网站菜单分类怎么做,wordpress黄页插件,手机app免费下载,如何做网上销售网站正题
题目链接:https://www.luogu.com.cn/problem/P6623 题目大意
一棵树#xff0c;每个节点有一个权值valival_ivali#xff0c;定义disi,jdis_{i,j}disi,j表示iii到jjj的距离。
一个节点xxx的权值定义为该节点子树中的每个节点yyy的disx,yvaljdis_{x,y}val_{j}disx…正题
题目链接:https://www.luogu.com.cn/problem/P6623 题目大意
一棵树每个节点有一个权值valival_ivali定义disi,jdis_{i,j}disi,j表示iii到jjj的距离。
一个节点xxx的权值定义为该节点子树中的每个节点yyy的disx,yvaljdis_{x,y}val_{j}disx,yvalj的异或和。
求所有节点的权值和 解题思路
对于一个二进制010101串我们可以用TrieTrieTrie从高位到低位存我们记录TrieTrieTrie上每个位置的答案考虑如何让整个TrieTrieTrie上的数字111。
显然对于一个000指向的节点它会变成111对于111指向的节点它会变成000并且进位。也就是我们交换左右子树后再向原来111指向的节点进位。
这样我们就实现了一个可以插入数字或者全部111来维护答案的数据结构之后用树上启发式合并即可。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N6e510,M27;
struct node{int to,next;
}a[N];
int n,tot,cnt,ls[N],siz[N],son[N];
int w[N],s[N*M],v[N*M],ch[N*M][2],ed[N*M],z;
long long ans;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void Make(int x,int k){if(!x){xcnt;ch[x][0]ch[x][1]s[x]ed[x]v[x]0;}if(!k){s[x]^1;ed[x]^1;return;}Make(ch[x][k1],k1);s[x]s[ch[x][0]]^s[ch[x][1]]^ed[x];v[x](v[ch[x][0]]1)^((v[ch[x][1]]1)|s[ch[x][1]]);return;
}
void Merge(int x){if(!x){return;}swap(ch[x][0],ch[x][1]);if(ed[x]!ch[x][1]){ch[x][1]cnt;ch[cnt][0]ch[cnt][1]s[cnt]ed[cnt]v[cnt]0;}ed[ch[x][1]]^ed[x];s[ch[x][1]]^ed[x];ed[x]0;Merge(ch[x][0]);s[x]s[ch[x][0]]^s[ch[x][1]]^ed[x];v[x](v[ch[x][0]]1)^((v[ch[x][1]]1)|s[ch[x][1]]);return;
}
void dfs(int x){siz[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;dfs(y);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
void calc(int x,int dep){Make(z,w[x]dep);for(int ils[x];i;ia[i].next){int ya[i].to;calc(y,dep1);}return;
}
void solve(int x){for(int ils[x];i;ia[i].next){int ya[i].to;if(yson[x])continue;solve(y);}cntz0;if(son[x])solve(son[x]),Merge(z);for(int ils[x];i;ia[i].next){int ya[i].to;if(yson[x])continue;calc(y,1);}Make(z,w[x]);ansv[1];return;
}
int main()
{freopen(tree2.in,r,stdin);scanf(%d,n);for(int i1;in;i)scanf(%d,w[i]);for(int i2;in;i){int x;scanf(%d,x);addl(x,i);}dfs(1);solve(1);printf(%lld,ans);
}
