题解 P6623 【[省选联考 2020 A 卷] 树】

_虹_

2020-06-23 17:27:14

Solution

~~思路题~~ 发现只需要+1,我们从低位到高位建立0/1trie。 那么每次全局+1,我们只要沿着右儿子走,回溯时候递归交换左右儿子去模拟进位就行了。 异或和可以在trie树上用类似树形dp的东西维护。 线段树合并(0/1trie合并)空间复杂度是$2nlogn$的,这里似乎卡内存了。 但是我们用不到历史版本,所以我们遇到重复节点只要把一个并到另一个上就行了,不需要新建节点。 时空复杂度O(nlogn) ~~跟12省联考d2t2一样属于福利题。~~ ```cpp #include <iostream> #include <list> using namespace std; const int kmaxn=600000+5; list<int> to[kmaxn]; void add_edge(int s,int d) { to[s].push_back(d); } struct node { int cnt; int res; int dep; int son[2]; }; node T[kmaxn*22]; int tot; void upd(int p) { int ls=T[p].son[0]; int rs=T[p].son[1]; T[p].res=T[ls].res ^ T[rs].res ^ ((T[rs].cnt&1)<<T[p].dep); } void ins(int& p,int i,int d) { if(!p) { p=++tot; T[p].dep=d; } ++T[p].cnt; if(d>20)return; bool dir=1&(i>>d); ins(T[p].son[dir],i,d+1); upd(p); } int merge(int dst,int src)//remeber to update the root array { if(!dst||!src) return dst?dst:src; T[dst].cnt+=T[src].cnt; T[dst].son[0]=merge(T[dst].son[0],T[src].son[0]); T[dst].son[1]=merge(T[dst].son[1],T[src].son[1]); upd(dst); return dst; } void add(int p) { if(!p||T[p].dep>20)return; add(T[p].son[1]); swap(T[p].son[1],T[p].son[0]); upd(p); } int rt[kmaxn]; int v[kmaxn]; int res[kmaxn]; void solve(int x) { for(list<int>::iterator i=to[x].begin();i!=to[x].end();++i) { solve(*i); rt[x]=merge(rt[x],rt[*i]); } add(rt[x]); ins(rt[x],v[x],0); res[x]=T[rt[x]].res; } int n; int tp; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;++i) { cin>>v[i]; } for(int i=2;i<=n;++i) { cin>>tp; add_edge(tp,i); } solve(1); long long ans=0; for(int i=1;i<=n;++i) { ans+=res[i]; } cout<<ans<<endl; return 0; } /* 5 5 4 1 2 3 1 1 2 2 */ ``` 听说有$O(nlog^2n)$做法,不知道那种做法能不能处理边权不为1的情况。。。。。