hdu 5606 tree(집합)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=5606
tree
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1183    Accepted Submission(s): 527
Problem Description
There is a tree(the tree is a connected graph which contains 
n  points and 
n−1  edges),the points are labeled from 1 to 
n ,which edge has a weight from 0 to 1,for every point 
i∈[1,n] ,you should find the number of the points which are closest to it,the clostest points can contain 
i  itself.
 
Input
the first line contains a number T,means T test cases.
for each test case,the first line is a nubmer 
n ,means the number of the points,next n-1 lines,each line contains three numbers 
u,v,w ,which shows an edge and its weight.
T≤50,n≤105,u,v∈[1,n],w∈[0,1]
 
Output
for each test case,you need to print the answer to each point.
in consideration of the large output,imagine 
ansi  is the answer to point 
i ,you only need to output,
ans1 xor ans2 xor ans3.. ansn .
 
Sample Input

   
   
   
   

    
    
    
    1
3
1 2 0
2 3 1
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1

in the sample.

$ans_1=2$

$ans_2=2$

$ans_3=1$

$2~xor~2~xor~1=1$,so you need to output 1.
   
   
   
   

 
Source
BestCoder Round #68 (div.2)
제목 의 대의:
한 개의 나무(n 개의 점,n-1 개의 변 의 연결 도)가 있 고 한 개의 나무(n 개의 점,n-1 개의 변 의 연결 도)가 있 습 니 다.표 시 는 1~n 이 고 나무의 변 권 은 0 또는 1 입 니 다.각 점 에서 가장 가 까 운 점 개수(자신 포함)를 구하 십시오.
문제 풀이 사고:처음에 w 를 0 으로 판단 하면 된다 고 생각 했 어 요.w 가 0 일 때 연 결 된 이 두 가지 점 에 모두 1 처 리 를 해 주 고 마지막 에 그 자체 의 이 점 을 더 하면 답 이에 요!!근 데 이 건 틀 렸 어!!ｗｒｏｎｇ　ａｎｓｗｅｒ！！！
다음 설명:예 를 들 어:
    １
　４
　１　２　０
　２　３　０
140 이 데이터 라면 어떻게 처리 해 야 하나 요?위 와 같이 계산 하면 1 이라는 점 에 대해 서 는 가장 가 까 운 점 이 두 개 밖 에 없 지만 실제로는 세 개!!따라서 상기 방법 을 사용 할 수 없 기 때문에 집합 하 는 방법 을 사용 하고 w=0 만 있 으 면 연결 된다.개 수 를 계산 하면 된다.
코드 참조.

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int num[100010];
int fa[100010];

int Find(int x)
{
    if (x!=fa[x])
    {
        return fa[x]=Find(fa[x]);
    }
    return x;
}

void Unit(int x,int y)
{
    x=Find(x);
    y=Find(y);
    if (x!=y)
    {
        fa[x]=y;
        num[y]+=num[x];//      ，                    
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        for (int i=1; i<=n; i++)
            fa[i]=i,num[i]=1;
        int u,v,w;
        int s=0;
        for (int i=1; i<=n-1; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            if (w==0)
            {
                Unit(u,v);
            }
        }
        for (int i=1; i<=n; i++)
        {
            if (fa[i]==i&&num[i]%2==1)
                s=num[i]^s;
        }
        printf ("%d
",s);
    }
    return 0;
}