牛客练习赛32B Xor Path （树形dp）

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给定一棵n个点的树，每个点有权值 ${A_i}$ 。定义 ${\mathbb{path}(i,j)}$ 表示

到

的最短路径上，所有点的点权异或和。

对于 ${i=1\sim n-1,\ j=i+1\sim n}$ ，求所有 ${\mathbb{path}(i,j)}$ 的异或和。

输入描述:

第一行一个整数n。

接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。

第n+1行有n个整数，表示每个点的权值 ${A_i}$ 。

输出描述:

输出一个整数，表示所有

${\mathbb{path}(i,j)}$

的异或和，其中

${i=1\sim n-1,\ j=i+1\sim n}$

。

示例1

输入

输出

说明

${mathbb{path}(1,2)=A_1 mathbb{xor} A_2=3\ mathbb{path}(1,3)=A_1 mathbb{xor} A_3=2\ mathbb{path}(1,4)=A_1 mathbb{xor} A_4=5\ mathbb{path}(2,3)=A_2 mathbb{xor} A_1 mathbb{xor} A_3=0\ mathbb{path}(2,4)=A_2 mathbb{xor} A_1 mathbb{xor} A_4=7\ mathbb{path}(3,4)=A_3 mathbb{xor} A_1 mathbb{xor} A_4=6}$

再将这6个数异或起来就可以得到答案5了。

备注:

${1\leq n\leq5\times10^5,0\leq A_i\leq10^9}$

题目大意：

给你一棵树，每个节点有一个权值。path[i,j]记录i到j的最短路径上所有节点权值的抑或。求所有path[i,j]的抑或（i=1~n-1,j=i+1~n）。注意(i,j)是有序实数对哦。

其实就是求每个点在所有最短路径中经历了几次。

树形dp就好了。假设1是树的根，sum[]记录子树的大小。dp过程还是有点妙哒。见代码。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
typedef long long ll;
const int mod=1000000007;
const int inf=1000000000;
const int maxn=500000;
const int maxm=200;

int n;
int to[maxn*2+5];
int next[maxn*2+5];
int head[maxn+5],cnt;
int val[maxn+5];
ll times[maxn+5];

int dfs(int x,int fa)
{
    int sum=0;
    for(int i=head[x];i!=-1;i=next[i])
    {
        int l=to[i];
        if(l!=fa)
        {
            int temp=dfs(l,x);
            times[x]+=(ll)sum*temp;
            sum+=temp;
        }
    }
    times[x]+=(ll)sum*(n-1-sum);
    times[x]+=n-1;
    return sum+1;
}

int main()
{
    scanf("%d",&n);
    memset(head,-1,sizeof(head));
    cnt=0;
    for(int i=1,a,b;i<=n-1;i++)
    {
        scanf("%d%d",&a,&b);
        to[cnt]=b;next[cnt]=head[a];head[a]=cnt++;
        to[cnt]=a;next[cnt]=head[b];head[b]=cnt++;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",val+i);

    memset(times,0,sizeof(times));
    dfs(1,-1);

    int ans=1^1;
    for(int i=1;i<=n;i++)
    {
        if(times[i]%2==0)
        {
            val[i]^=val[i];
        }
        ans^=val[i];
        //printf("%lld %d
",times[i],ans);
    }

    printf("%d
",ans);

    return 0;
}

View Code