题目链接：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 nubmern ,means
the number of the points,next n⑴ 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@H_403_263@,1]
for each test case,the first line is a nubmer
Output
for each test case,you need to print the answer to each point.
in consideration of the large output,imaginean@H_177_301@si is
the answer to point i ,you
only need to output,a@H_404_356@ns1 xor ans2@H_184_404@ xor ans3.. ansn .
in consideration of the large output,imagine
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)
题目大意：
有1个树（n个点，n⑴条边的连通图），有1个树(n个点,n−1条边的联通图),点标号从1~n,树的边权是0或1.求离每一个点最近的点个数(包括自己).
解题思路：1开始想着只要判断ｗ为０就行了，ｗ为０的时候直接给连通的这两个点都加１处理，最后再加上本身这个点就是答案了！！但是这个是毛病的！！！ｗｒｏｎｇ ａｎｓｗｅｒ！！！
下面解释1下：举1个例子：
１
４
１ ２ ０
２ ３ ０
１ ４ ０如果是这组数据的话，我们需要怎样处理呢？如果依照上陈述法计算的话，对１这个点，与其最近的点只有两个，但实际上有3个！！所以就不可以采取上述方法，所以采取并查集的方法，只要ｗ＝０就给连通起来。在计算个数便可。
详见代码。
#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⑴; 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\n",s);
}
return 0;
}
