题解 P6623 【[省选联考 2020 A 卷] 树】
_虹_
2020-06-23 17:27:14
~~思路题~~
发现只需要+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的情况。。。。。