Xor Path
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给定一棵n个点的树，每个点有权值A i。定义path(i,j)表示i 到j 的最短路径上，所有点的点权异或和。
对于i=1∼n−1, j=i+1∼n，求所有path(i,j)的异或和。
输入描述:
第一行一个整数n。 接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。 第n+1行有n个整数，表示每个点的权值A i。
输出描述:
输出一个整数，表示所有{\mathbb{path}(i,j)}path(i,j)的异或和，其中 i=1∼n−1, j=i+1∼n。
示例1
输入
复制
4
1 2
1 3
1 4
1 2 3 4
输出
复制
5
题解：
根据异或的性质，一个数异或两次就没了，所以一个点异或两次（偶数次）就相当于没有。所以我们只需要统计每个点被异或了多少次
我们考虑一下一个点x会有多少种情况：
size[x]表示以x为根的子树内有多少点
- x作为一个路径的顶点 ，那么就要与剩下的点直接连接，所以就是n-1
- 当x为根时，x的两个子树（其中一个子树名为y）中任意点进行连接。那么就是他子树的节点个数两两相乘。子树所有点为size[x]-1,子树y：size[y],剩余点为size[x]-1-size[y]，最后两个相乘size[y]×(n−1−size[y]) y是动态取值，
- 当x不为根时， x的子树与x的父亲节点的子树（除了x之外的）之间的路径经过该点的次数。子树点个数为size[x]-1，非子树个数为n-size[x],总数就是(size[x]−1)×(n−size[x])
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int size[maxn];
int a[maxn],sum;
vector<int>g[maxn];
typedef long long ll;
int n;
void dfs(int u,int fa)
{
size[u]=1;
ll res=0;//记录奇偶次数
for(auto x:g[u])
{
if(x==fa)continue;
dfs(x,u);
size[u]+=size[x];//更新以u为根的树的大小
res+=1ll*(size[u]-size[x]-1)*size[x];//我们只需要知道奇偶性即可
}
res+=1ll*(size[u]-1)*(n-size[u]);//第三种情况
// res>>=1;//多计算了一遍
res+=n-1; //第一种情况
if(res&1)//如果为奇数记入结果
sum^=a[u];
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
cin>>a[i];//点值
}
dfs(1,0);//从第一个点开始
cout<<sum<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int size[maxn];
int a[maxn],sum;
vector<int>g[maxn];
typedef long long ll;
int n;
void dfs(int u,int fa)
{
size[u]=1;
ll res=0;//记录奇偶次数
for(auto x:g[u])
{
if(x==fa)continue;
dfs(x,u);
res+=1ll*(n-size[x]-1)*size[x];//我们只需要知道奇偶性即可
size[u]+=size[x];//更新以u为根的树的大小
}
res+=1ll*(size[u]-1)*(n-size[u]);//第一和第三种情况
res>>=1;//多计算了一遍
res+=n-1;
if(res&1)//如果为奇数记入结果
sum^=a[u];
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
cin>>a[i];//点值
}
dfs(1,0);//从第一个点开始
cout<<sum<<endl;
return 0;
}
京公网安备 11010502036488号