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

Hint

in the sample.

• ans_1=2
• ans_2=2
• ans_3=1

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

題意：給出 t 組數據，每組數據給出一個整數 n 代表有 n 個點 n-1 條邊，然后依次給出 n-1 條邊及其權值（僅有 0、1），要統計每個點距離他最近的點的個數（包括其自身），最后將每個點距離他最近的個數異或后輸出

思路：由于要統計距離每個點最近的點的個數，且邊的權值僅有 0、1，因此可以考慮當邊權為 0 時，使用并查集將點連接，邊權為 1 時，不進行任何操作，這樣將所有的點可劃分為多個連通塊，然后統計每個點所在的連通塊中的點的個數即可，最后將所有點的值異或輸出。

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-6 #define MOD 16007 #define INF 0x3f3f3f3f #define N 1000001 #define LL long long using namespace std; int father[N]; int num[N]; int Find(int x){while(father[x]!=x)x=father[x];return x; } void Union(int x,int y){x=Find(x);y=Find(y);if(x!=y)father[x]=y;num[y]+=num[x]; } int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);memset(num,0,sizeof(num));for(int i=1;i<=n;i++)father[i]=i;int m=n-1;for(int i=0;i<m;i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);if(w==0)Union(x,y);}for(int i=1;i<=n;i++){//枚舉每個點father[i]=Find(i);//尋找每個點的父節點num[father[i]]++;//統計子節點個數（包括其自身）}for(int i=1;i<=n;i++)//統計父節點外的點的個數num[i]=num[father[i]];int res=0;for(int i=1;i<=n;i++)//將所有點的值異或res^=num[father[i]];printf("%d\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的Tree（HDU-5060）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。