This way
題意：
給你一棵樹，統計
題解：
這個知識點很基礎嗎，為什么大家都會啊
就是dfs做的時候，先做輕兒子，然后將輕兒子的影響消除之后，做重兒子，重兒子的影響不消除，這道題目要注意的就是做當前點的時候，要先將一個兒子的子樹做完之后再將影響加入，否則有可能會一個子樹內部匹配
dfs1是搜索重兒子
dfs2是做每個節點，f_ans是求每個節點的答案，add是在每個子樹搜索完成之后，將這個子樹的影響加入，
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=(1<<20)+50;
int cnt[N][20][2],mx,a[N/10],son[N/10],siz[N/10],stay;
ll sum;
struct node{
int to,next;
}e[N*2/10];
int tot,head[N/10];
void add(int x,int y){
e[tot].to=y;
e[tot].next=head[x];
head[x]=tot++;
}
ll ans;
void dfs1(int u,int fa)
{
siz[u]=1;
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa)
{
dfs1(v,u);
siz[u]+=siz[v];
if (son[u]==0||siz[v]>siz[son[u]])
son[u]=v;
}
}
}
void add(int x,int fa,int v){
for(int i=0;i<20;i++)
cnt[a[x]][i][(x>>i)&1]+=v;
for(int i=head[x];~i;i=e[i].next){
int ne=e[i].to;
if(ne==fa||ne==stay)continue;
add(ne,x,v);
}
}
void f_ans(int rt,int x,int fa,int v){
int val=a[x]^a[rt];
if(v==1)
for(int i=0;i<20;i++)
ans+=1ll*cnt[val][i][!((x>>i)&1)]*(1ll<<i);
if(x==rt){
for(int i=0;i<20;i++)
cnt[a[x]][i][(x>>i)&1]+=v;
}
for(int i=head[x];~i;i=e[i].next){
int ne=e[i].to;
if(ne==fa||ne==stay)continue;
f_ans(rt,ne,x,v);
if(x==rt)
add(ne,x,v);
}
}
void dfs2(int x,int fa,int is_son){
for(int i=head[x];~i;i=e[i].next){
int ne=e[i].to;
if(ne==fa||ne==son[x])continue;
dfs2(ne,x,0);
}
if(son[x])dfs2(son[x],x,1),stay=son[x];
f_ans(x,x,fa,1);
//ans[x]=sum;
stay=0;
if(!is_son)f_ans(x,x,fa,-1);
}
int main()
{
memset(head,-1,sizeof(head));
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int x,y;
for(int i=1;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs1(1,0);
dfs2(1,0,1);
printf("%lld\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/211690.html
標籤：其他