HDOJ 5606-tree【并查集】

た入场券 2022-08-20 06:19 31阅读 0赞

# tree #

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 894 Accepted Submission(s): 420

Problem Description

There is a tree(the tree is a connected graph which contains  n![Image 1][] points and  n−1![Image 1][] edges),the points are labeled from 1 to  n![Image 1][],which edge has a weight from 0 to 1,for every point  i∈\[1,n\]![Image 1][],you should find the number of the points which are closest to it,the clostest points can contain  i![Image 1][] itself.

Input

the first line contains a number T,means T test cases.  
  
for each test case,the first line is a nubmer  n![Image 1][],means the number of the points,next n-1 lines,each line contains three numbers  u,v,w![Image 1][],which shows an edge and its weight.  
  
 T≤50,n≤10![Image 1][]5![Image 1][],u,v∈\[1,n\],w∈\[0,1\]![Image 1][]

Output

for each test case,you need to print the answer to each point.  
  
in consideration of the large output,imagine  ans![Image 1][]i![Image 1][]![Image 1][] is the answer to point  i![Image 1][],you only need to output,  ans![Image 1][]1![Image 1][]xorans![Image 1][]2![Image 1][]xorans![Image 1][]3![Image 1][]..ans![Image 1][]n![Image 1][]![Image 1][].

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) ][BestCoder Round _68 _div.2_]

解题思路：

有一个树(n个点, n−1条边的联通图),点标号从1-n,树的边权是0或1.求离每个点最近的点个数(包括自己)。

由题意可得，当权值为1时这两边是不会联通的，因为这一点到自己的距离始终唯0，所以这一点只有到距离为0常能联通。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define M 100002
    using namespace std;
    int n;
    int fa[M],arr[M];
    void init()
    {
    	int i,j;
    	for(i=1;i<=n;i++)
    	{
    		fa[i]=i;
    		arr[i]=1;
    	}
    }
    int find(int x)
    {
    	int r=x;
    	while(r!=fa[r])
    	{
    		r=fa[r];
    	}
    	return r;
    }
    void join(int x,int y)
    {
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy)
    	{
    		fa[fx]=fy;
    		arr[fy]+=arr[fx];
    	}
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		scanf("%d",&n);
    		init();
    		int i,j;
    		for(i=0;i<n-1;i++)
    		{
    			int x,y,w;
    			scanf("%d%d%d",&x,&y,&w);
    			if(w==1)
    			{
    				continue;
    			}
    			else
    			{
    				join(x,y);
    			}
    		}	
    		int ans=arr[find(1)];
    		for(i=2;i<=n;i++)
    		{
    			ans^=arr[find(i)];//异或运算 
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[Image 1]: 
[BestCoder Round _68 _div.2_]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2368+%28div.2%29&source=1&searchmode=source