题目链接：[点击打开链接](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; } ~~~