Tree Intersection 【CSU - 1811】【Dsu on Tree】

中南大学OJ 题目链接

题意：

  给定一棵树，它有n-1条边。如果把第i条边删掉之后，会形成两个联通块。你需要回答有多少种颜色同时出现在这两个联通块中。

  有不超过15组测试数据。 

  对于每组测试数据，第一行一个整数n，表示树的大小。 

  接下来一行n个数，表示每个节点的颜色。 

  接下来n-1行，表示第i条边，连接的两个节点。

  输出n-1行，表示删除第i条边之后，同时出现在两个联通块中的颜色数量。

思路：

  看一下，我们可以把问题转换到子树上去，我们断开一条边，会形成两个子树，如果说子树上的存在的颜色的数量不到总的颜色的数量，说明这个颜色产生了价值，我们直接记录这个价值即可。然后因为是对于子树上的操作，所以我们可以利用Dsu on Tree来进行维护。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, col[maxN], sum_col[maxN], head[maxN], cnt;
struct Eddge
{
    int nex, to, id;
    Eddge(int a=-1, int b=0, int c=0):nex(a), to(b), id(c) {}
}edge[maxN << 1];
inline void addEddge(int u, int v, int edge_id)
{
    edge[cnt] = Eddge(head[u], v, edge_id);
    head[u] = cnt++;
}
inline void _add(int u, int v, int id) { addEddge(u, v, id); addEddge(v, u, id); }
int siz[maxN], dfn[maxN], tot, rid[maxN], Wson[maxN], deep[maxN];
int Ques[maxN] = {0};
void pre_dfs(int u, int fa)
{
    dfn[u] = ++tot; rid[tot] = u; siz[u] = 1; Wson[u] = 0;
    int maxx = 0;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa) continue;
        deep[v] = deep[u] + 1;
        Ques[v] = edge[i].id;
        pre_dfs(v, u);
        siz[u] += siz[v];
        if(maxx < siz[v])
        {
            maxx = siz[v];
            Wson[u] = v;
        }
    }
}
int ss, now_col[maxN], ans[maxN];  //cop_S记录总的颜色种类
void dfs(int u, int fa, bool keep)
{
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa || v == Wson[u]) continue;
        dfs(v, u, false);
    }
    if(Wson[u])
    {
        dfs(Wson[u], u, true);
    }
    for(int i=head[u], v, id; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == Wson[u] || v == fa) continue;
        for(int j=dfn[v]; j<dfn[v] + siz[v]; j++)
        {
            id = rid[j];
            now_col[col[id]]++;
            if(now_col[col[id]] == sum_col[col[id]] && (now_col[col[id]] ^ 1)) ss--;
            else if(now_col[col[id]] == 1 && (now_col[col[id]] ^ sum_col[col[id]])) ss++;
        }
    }
    now_col[col[u]]++;
    if(now_col[col[u]] == sum_col[col[u]] && (now_col[col[u]] ^ 1)) ss--;
    else if(now_col[col[u]] == 1 && (now_col[col[u]] ^ sum_col[col[u]])) ss++;
    if(u ^ 1) ans[Ques[u]] = ss;
    if(!keep)
    {
        ss = 0;
        for(int i=dfn[u], v; i < dfn[u] + siz[u]; i++)
        {
            v = rid[i];
            now_col[col[v]] = 0;
        }
    }
}
inline void init()
{
    cnt = tot = ss = 0;
    for(int i=1; i<=N; i++)
    {
        head[i] = -1;
        sum_col[i] = now_col[i] = 0;
    }
}
int main()
{
    while(scanf("%d", &N) != EOF)
    {
        init();
        for(int i=1; i<=N; i++)
        {
            scanf("%d", &col[i]);
            sum_col[col[i]] ++;
        }
        for(int i=1, u, v; i<N; i++)
        {
            scanf("%d%d", &u, &v);
            _add(u, v, i);
        }
        pre_dfs(1, 0);
        dfs(1, 0, false);
        for(int i=1; i<N; i++)
        {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}