HDU 5606 tree（并查集）
最后更新于：2022-04-01 15:53:23
题目链接：[点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=5606)
题意：一棵树，权值只有0和1，找到每个点与之相距最近的点的个数， （包括这个点自己，也就是说，等价于找每个点与之相距为0的点的个数）。
用并查集乱搞就行了， 如果边权为0就合并集合， 并在集合的根节点上维护一个信息：该集合中点的个数。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100000 + 10;
int T,n,m,ans[maxn],p[maxn];
struct node {
int a, b, c;
node(int aa=0, int bb=0, int cc=0):a(aa), b(bb), c(cc) {}
}a[maxn];
int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); }
int solve() {
for(int i=1;i<=n;i++) p[i] = i, ans[i] = 1;
for(int i=1;i<=n-1;i++) {
int x = _find(a[i].a), y = _find(a[i].b);
if(!a[i].c) {
p[x] = y;
ans[y] += ans[x];
}
}
int hehe = 0;
for(int i=1;i<=n;i++) {
int x = _find(i);
hehe ^= ans[x];
}
return hehe;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n-1;i++) {
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
}
printf("%d\n",solve());
}
return 0;
}
~~~