題目鏈接：[點擊打開鏈接](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; } ~~~