bestcoder#68 div 2 tree【集計】

tree  
 Accepts: 152
 
 Submissions: 697
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
問題の説明

    (nn  , n-1n−1      ),    11~nn,     00 11.           (    ).

説明の入力

       TT,  TT   .
      ,      nn,     ,   n-1n−1,      u,v,wu,v,w,              .
T = 50,1 \leq n \leq 100000, 1 \leq u,v \leq n,0 \leq w \leq 1T=50,1≤n≤100000,1≤u,v≤n,0≤w≤1.

出力の説明

      ,    .
         , ans_ians​i​​   ii     .     ans_1 \ xor \ ans_2 \ xor \ ans_3.. \ xor \ ans_nans​1​​ xor ans​2​​ xor ans​3​​.. xor ans​n​​  .

入力サンプル

1
3
1 2 0
2 3 1

出力サンプル

1

Hint

ans_1 = 2ans​1​​=2
ans_2 = 2ans​2​​=2
ans_3 = 1ans​3​​=1
2 \ xor \ 2 \ xor \ 1=12 xor 2 xor 1=1,     11.

终わらないうちに问题解を出すのはちょっとテンションが高いですね低調~1 A漂っています
コレクションを調べてもう一つのレコードコレクション要素の個数の配列を維持し、マージするたびに更新すればいいのです.

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,t,a[100005],num[100005],cnt;
int fnd(int x)
{
    if(x!=a[x]) a[x]=fnd(a[x]);
    return a[x];
}
void addto(int x,int y)
{
    x=fnd(x),y=fnd(y);
    if(x==y) {
        return ;
    }
    a[y]=a[x];
    num[x]+=num[y];
    return ;
}
int main()
{
  //  freopen("cin.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cnt=0;
        for(int i=1;i<=n;i++) {num[i]=1;a[i]=i;}
        for(int i=1;i<n;i++)
        {
            int u,v,q;
            scanf("%d%d%d",&u,&v,&q);
            if(q==0)  addto(u,v);
        }
        //cout<<"44544"<<endl;
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==i&&(num[i]&1)) cnt^=num[i];
        }
        printf("%d
",cnt);
    }
    return 0;
}