2829_Tree_模拟

发布于 2017-11-07  12 次阅读


题目描述

思路

我们考虑当一个节点的颜色和他的父节点不向同时,这个节点肯定是要被反色的,所以我们直接for一下全部点统计一下答案就可以了

#include 
#include 
#include 
using namespace std;
#define N 700001
struct edge
{
    int to, next;
}e[N];
int l = 0;
int a[N], ls[N], ans[N], fa[N];
int cmp(int a, int b)
{
    return a < b;
}
int bfs()
{
    queue t;
    t.push(1);
    while (!t.empty())
    {
        int now = t.front();
        t.pop();
        if (a[fa[now]] != a[now])
            ans[++l] = now;
        for (int i = ls[now]; i; i = e[i].next)
        {
            t.push(e[i].to);
        }
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        fa[y] = x;
        e[i] = (edge) {y, ls[x]};
        ls[x] = i;
    }
    bfs();
    sort(ans + 1, ans + l + 1, cmp);
    for (int i = 1; i <= l; i++)
        printf("%d ", ans[i]);
    printf("\n");
}

 

]]>


「墨泼三千烟火,许你一世迷离」