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

Tabris

CSDNhdubestcoder数学

发布于：2016年4月29日

次浏览

[原创]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;
}

本页文档最后更新于：2021年5月16日

CSDN

数学

HDU

bestcoder

思维

hdu-5606