Noble 的博客

Noble 的博客

♡虹蓝♡

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

posted on 2020-06-23 17:27:14 | under 题解 |

思路题

发现只需要+1,我们从低位到高位建立0/1trie。

那么每次全局+1,我们只要沿着右儿子走,回溯时候递归交换左右儿子去模拟进位就行了。

异或和可以在trie树上用类似树形dp的东西维护。

线段树合并(0/1trie合并)空间复杂度是$2nlogn$的,这里似乎卡内存了。

但是我们用不到历史版本,所以我们遇到重复节点只要把一个并到另一个上就行了,不需要新建节点。

时空复杂度O(nlogn)

跟12省联考d2t2一样属于福利题。

#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的情况。。。。。