[原创]HDU 5606 tree BestCoder Round #68 (div.2) [思维]【数学】

2016-04-29 21:34:59 Tabris_ 阅读数：291

博客爬取于2020-06-14 22:44:29
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51284402

题目链接 ：http://acm.hdu.edu.cn/showproblem.php?pid=5606

tree Accepts: 143 Submissions: 807
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
问题描述
有一个树(nn个点, n-1n−1条边的联通图),点标号从11~nn,树的边权是00或11.求离每个点最近的点个数(包括自己).
输入描述
第一行一个数字TT,表示TT组数据.
对于每组数据,第一行是一个nn,表示点个数,接下来n-1n−1,每行三个整数u,v,wu,v,w,表示一条边连接的两个点和边权.
T = 50,1 <= n <= 100000, 1 <= u,v <=n,0 <= w <= 1T=50,1≤n≤100000,1≤u,v≤n,0≤w≤1.
输出描述
对于每组数据,输出答案.
考虑到输出规模过大,设ans_ians
i
表示第ii个点的答案.你只需输出ans_1 ^ ans_2 ^ ans_3^ans_nans

1
xor ans
2
xor ans
3
… xor ans
n
即可.
输入样例
1
3
1 2 0
2 3 1

输出样例
1

Hint
ans_1 = 2ans
1
=2
ans_2 = 2ans
2
=2
ans_3 = 1ans
3
=1
2 \ xor \ 2 \ xor \ 1=12 xor 2 xor 1=1, 因此输出11.

题目大意 ： 如题 中文体面。。。。

解题思路 ： 题目说 找到每个点离自己最近的点的个数 而且还包括自己 自己与自己的距离 就是0 没有疑议
所以就找到与自己距离为0的点的个数即可

但是数据达到了10^6 如果两层for的话必定会超时 所以不可以暴力解

这时思考 一个点与其距离为0的点的个数和 是对每一个点都成立的
比如说 点1 点2 点3 互相距离为0
所以ans1=3 ans2=3 ans3=3；
就是有几个点 他们有的ans值都相同
这样之求解出这些点的一个的ans值就行
然后在求解出ans个ans的自身异或 值
Ps： ans个ans的自身异或 值
很简单 只要判断ans的奇偶即可 ans为偶数 那么异或的结果为0 ans为奇数 异或值即为ans本身

在这里 我求解这些互相距离为0的点 采用的是并查集 把距离相同且为0 的点归为统一集合
之后在遍历一遍 记录每个集合的个数（即ans）即可 、

然后再把这些ans值互相异或即可

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <queue>
# include <vector>
# include  <math.h>
# define EPS 1e-8
# define MAXN 30
# define MAXM 31

using namespace std;
int pre[100005];
int   b[100005];
int fin(int x)
{
    int r=x;
    while(r!=pre[r])
        r=pre[r];

    int i=x,j;
    while(i!=j)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}
int join(int x,int y)
{
    int fx=fin(x),fy=fin(y);

    if(fx!=fy)
        pre[fy]=fx;
}

int solve(int x)
{
    if(x%2==0)
        return 0;
    else
        return x;
}

int main()
{
    int t ;
    scanf("%d",&t);
    while(t--)
    {
        memset(b,0,sizeof(b));
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            pre[i]=i;

        int u,v,w;
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            if(!w)    join(u,v);
        }

        for(int i=1;i<=n;i++)
        {
            b[pre[i]]++;
        }

        int flag=0,sum=0;

        for(int i=1;i<=n;i++)
        {
          //printf("%d-->%d\n",i,b[i]);
            if(b[i])
                sum^=solve(b[i]);
        }
        printf("%d/n",sum);
    }
    return 0;
}