BestCoder Round #68 (div.2) 1002 tree

题意:给你一个图,每条边权值0或1,问每个点周围最近的点有多少个?

思路:并查集找权值为0的点构成的连通块。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #define clc(a,b) memset(a,b,sizeof(a))
 7 using namespace std;
 8 int pre[100010],a[100010];//标记根节点
 9 int find(int x)//查找根节点
10 {
11     int r=x;
12     while(pre[r]!=r)//返回根节点r
13         r=pre[r];
14     int i=x,j;
15     while(i!=r)//路径压缩
16     {
17         j=pre[i];//在改变上级之前用临时变量j记录下他的值
18         pre[i]=r;//把上级改为根节点
19         i=j;
20     }
21     return r;
22 }
23 void join(int x,int y)//判断x,y是否连通.如果已经连通,就不用管了;如果不连通,就把它们所在的连通分支合并起
24 {
25     int fx=find(x),fy=find(y);
26     if(fx!=fy) pre[fy]=fx;
27 }
28 int main()
29 {
30     //freopen("in.txt","r",stdin);
31     int t,n,x,y,z;
32     while(~scanf("%d",&t))
33     {
34         for(int i=0; i<t; i++)
35         {
36             clc(a,0);
37             scanf("%d",&n);
38             for(int i=1; i<=n; i++)
39             {
40                 pre[i]=i;
41             }
42             for(int i=1; i<n; i++)
43             {
44                 scanf("%d%d%d",&x,&y,&z);
45                 if(!z) join(x,y);
46             }
47             for(int i=1; i<=n; i++)
48             {
49                 a[find(i)]++;
50             }
51             long long ans=0;
52             for(int i=1; i<=n; i++)
53             {
54                 int p=a[find(i)];
55                 if(p) ans^=p;
56                 else ans^=1;
57             }
58             printf("%I64d\n",ans);
59         }
60     }
61     return 0;
62 }

时间: 01-01

BestCoder Round #68 (div.2) 1002 tree的相关文章

HDU 5671 Matrix (BestCoder Round #81 (div.2) 1002)

传送门 Matrix Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 311    Accepted Submission(s): 142 Problem Description There is a matrix M that has n rows and m columns (1≤n≤1000,1≤m≤1000).Then we

BestCoder Round #50 (div.2)

题目传送:BestCoder Round #50 (div.2) BC感觉越做越无语了 1001.Distribution money AC代码: #include <map> #include <set> #include <list> #include <cmath> #include <deque> #include <queue> #include <stack> #include <bitset> #

hdu5418 BestCoder Round #52 (div.2) Victor and World ( floyd+状压dp)

Problem Description After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are n countries on the earth, which are numbered from 1 to

BestCoder Round #11 (Div. 2) 前三题题解

题目链接: huangjing hdu5054 Alice and Bob 思路: 就是(x,y)在两个參考系中的表示演全然一样.那么仅仅可能在这个矩形的中点.. 题目: Alice and Bob Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 216    Accepted Submission(s): 166 Problem De

BestCoder Round #11 (Div. 2) 题解

HDOJ5054 Alice and Bob Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 302    Accepted Submission(s): 229 Problem Description Bob and Alice got separated in the Square, they agreed that if they

HDU 5651 xiaoxin juju needs help(BestCoder Round #77 (div.1)1001)

传送门 xiaoxin juju needs help Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 861    Accepted Submission(s): 243 Problem Description As we all known, xiaoxin is a brilliant coder. He knew **palin

BestCoder Round #69 (div.2) Baby Ming and Weight lifting(hdu 5610)

Baby Ming and Weight lifting Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 681    Accepted Submission(s): 280 Problem Description Baby Ming is fond of weight lifting. He has a barbell pole(the

BestCoder Round #81 (div.2) B Matrix

B题...水题,记录当前行是由原矩阵哪行变来的. 1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<iostream> 5 #include<queue> 6 #include<stack> 7 #include<cmath> 8 #include<algorithm> 9 #include<malloc.h>

BestCoder Round #62 (div.2) 1004

好长时间没做比赛了,原来就菜现在更菜,1004的题目没想到div.2赛后只有一个人做出来,做题的时候想到了做法但时间不多自己的奇葩代码不足以在比赛时间debug出来,赛后补了一发: 题目&提交地址在这:http://acm.hdu.edu.cn/showproblem.php?pid=5565 const int INF = 1000000000; const double eps = 1e-8; const int maxn = 10000000 + 10; const int mod = 1