HDU 5606 tree 并查集

tree

把每条边权是1的边断开,发现每个点离他最近的点个数就是他所在的连通块大小.

开一个并查集,每次读到边权是0的边就合并.最后Ans​i​​=size[findset(i)],size表示每个并查集根的size

Ans_i=size[findset(i)],sizeAns​i​​=size[findset(i)],size表示每个并查集根的sizesize.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=100000+5;
int a[maxn];
int fa[maxn];
int find(int x)
{
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; ++i)
            fa[i]=i;
        for(int i=1; i<n; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            if(w==0)
            {
                int fx=find(u);
                int fy=find(v);
                if(fx==fy)continue;
                fa[fy]=fx;
            }
        }
        for(int i=1; i<=n; i++)
        {
            int f=find(i);
            a[f]++;
        }
        int ans=0;
        for(int i=1; i<=n; i++)
        {
           ans=(ans^a[fa[i]]);
        }
        printf("%d
",ans);
    }
    return 0;
}