题解 P6068 【[RC-02] XOR】

zhengrunzhe · 2020-02-06 14:01:40 · 题解

提供一个常数大的一个log解法

出题人把询问分为了一百万个换根和一百万个其余操作，其中前者要求O(1)

而我的这个全都是一个log，相当于两百万个问用log的方法解决，也许像树状数组常树小的能过，但我这个lct常数实在是大我最多就卡到90，但这不是问题，主要是提供一个思路。听说有两只log的树状数组开O2艹过去了

由于我不喜欢叫lct，叫S-T \ Trees

虚子树叫dashed，实链叫solid

首先看操作4:路径点权xorsum

S-T trees记下点权，维护实链的xorsum，expose提取路径返回即可

由于是有根树，expose需要evert换根，记下原本的root，expose之后把答案存下来，然后evert(root)把根换回去再返回答案

接着看操作3:lca

s-t trees上找lca有一种做法是先access(x)，然后执行access(y)，看最后切换虚实的点即lca

这种做法是没什么问题的，我这里用的是另一种做法

在root \ path上的non-local \ searching for \ LCA

一般的树上距离公式:dis(x,y)=dep_x+dep_y-2dep_{lca}+1

移项一下:2dep_{lca}=dep_x+dep_y-dis(x,y)+1

系数化为1:dep_{lca}=\frac {dep_x+dep_y-dis(x,y)+1}{2}

然后我们access(x)把x到根的路径提取出来，然后在上面找第dep_{lca}个点，即在root \ path找排名为dep_{lca}的点，类似平衡树上二分即可

操作5:子树xorsum

由于xorsum是可差分的，切换虚实链是可以通过xor掉原实儿子后xor新实儿子的，所以我们没有必要去写个toptree，直接s-t trees维护子树信息即可

考虑维护虚子树xorsum: dashed\_sum

s-t tree上的子树xorsum(树簇异或和)表示为sum

可以这么维护:sum=son[0]\rightarrow sum \bigoplus val \bigoplus son[1]\rightarrow sum \bigoplus dashed\_sum

考虑在access的时候把一个点q的右儿子q\rightarrow son[1]切换为p

异或原右儿子表示把原本的消除，后异或p表示加入p

然后要查询的点p的子树异或和subtree\_sum就是先access(p)，然后输出p \rightarrow dashed\_sum \bigoplus p \rightarrow val

操作1:换根+询问所有子树异或和的异或和

不妨先算出原本的所有子树的异或和的异或和，然后再考虑每个操作对答案的影响

3,4,5操作都是没有影响的，现在考虑换根带来的影响

考虑原根为v，把根换成u的影响，把v除到u路径的子树记作B，u的子树记作A，u,v的路径记作[u,v]，排除端点u,v的记作(u,v)，其中w为最上面的那个点,sum_x表示x的子树异或和

原本的答案记为sum_u \bigoplus ans(u,v) \bigoplus ans_C \bigoplus sum_v \bigoplus ans_B \bigoplus ans_A

新答案:sum_u' \bigoplus ans(u,v)' \bigoplus ans_C \bigoplus sum_v' \bigoplus ans_A \bigoplus ans_B

特别地,0=u,|(u,v)|+1=v,|(u,v)|=w

考虑一个点k的子树异或和咋变

首先k-1以下的部分倒过来变成k的祖先，所以sum_k\bigoplus=sum_{k-1}

其次在k上方的所有点倒过来在k的子树中，所以sum_k\bigoplus=sum_v \bigoplus sum_k

然后我们对于所有的k串在一起，发生的变化为:

由于异或有结合律合交换律，所以发现能删去一堆东西

中间的都可以消掉,最后由于异或偶数个相同的可以消除，所以化为

然后考虑最终答案变了什么

由于|(u,v)|=dep_u-2，奇偶性与dep_u相同

s-t trees维护实链长度solid_size，access(u)一下获取dep_u(即rootpath长度即solid_size)，sum_v就是整棵树的异或和，在操作2的时候变化

操作2:单点修改

这一个操作也是会影响操作1的答案的，考虑变化了什么

u到根路径上的所有点的子树异或和都消去了原来的点权加上了新的点权

所以直接access然后看dep_u的奇偶性，是奇数答案就异或上u\rightarrow val \bigoplus w

然后把u\rightarrow val赋成w即可

#include<cstdio>
template<class type>inline const void read(type &in)
{
    in=0;char ch(getchar());
    while (ch<48||ch>57)ch=getchar();
    while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
}
template<class type>inline const void swap(type &a,type &b){const type c(a);a=b;b=c;}
const int N(1e6+10);
namespace Sleator_Tarjan_Trees
{
    struct tree
    {
        bool rev;
        int solid_size,val,dashed_sum,solid_sum,sum;
        tree *son[2],*fa;
        static tree *null;
        void *operator new(size_t size);
        void *operator new[](size_t size);
        inline tree():rev(0),solid_size(0),val(0),dashed_sum(0),solid_sum(0)
        {
            static bool init(0);
            if (!init)
                init=1,
                null=new tree,
                null->son[0]=null->son[1]=null->fa=null;
            son[0]=son[1]=fa=null;
        }
        inline const void pushup()
        {
            solid_size=son[0]->solid_size+1+son[1]->solid_size;
            solid_sum=son[0]->solid_sum^val^son[1]->solid_sum;
            sum=son[0]->sum^val^son[1]->sum^dashed_sum;
        }
        inline const void reverse()
        {
            swap(son[0],son[1]);rev^=1;
        }
        inline const void pushdown()
        {
            if (rev)son[0]->reverse(),son[1]->reverse(),rev=0;
        }
        inline const bool isroot()
        {
            return fa->son[0]!=this&&fa->son[1]!=this;
        }
        inline const bool id()
        {
            return fa->son[1]==this;
        }
        inline const void set(tree *p,const bool &d)
        {
            (son[d]=p)->fa=this;
        }
        inline const void rotate()
        {
            fa->pushdown();pushdown();
            const bool f(id());
            tree *fa(this->fa),*gfa(fa->fa),*q(son[f^1]);
            if (!fa->isroot())gfa->son[fa->id()]=this;
            (son[f^1]=fa)->son[f]=q;
            ((q->fa=fa)->fa=this)->fa=gfa;
            fa->pushup();pushup();
        }
        inline const void splay()
        {
            for (pushdown();!isroot();rotate())
                if (!fa->isroot())
                    fa->fa->pushdown(),
                    (fa->id()^id()?this:fa)->rotate();
        }
    }*root,*node0,*tree::null;
    #define null tree::null
    inline tree *node(const int &x){return node0+x;}
    char memory_pool[N*sizeof(tree)],*tail(memory_pool+sizeof memory_pool);
    inline void *tree::operator new(size_t size){return tail-=size;}
    inline void *tree::operator new[](size_t size){return tail-=size;}
    inline const void access(tree *p)
    {
        p->splay();
        p->dashed_sum^=p->son[1]->sum;
        p->son[1]=null;
        p->pushup();
        for (tree *q(p->fa);q!=null;q=p->fa)
            q->splay(),
            q->dashed_sum^=q->son[1]->sum,
            q->dashed_sum^=(q->son[1]=p)->sum,
            q->pushup(),
            p->rotate();
    }
    inline const void evert(tree *p)
    {
        access(p);p->reverse();
    }
    inline const void expose(tree *p,tree *q)
    {
        evert(p);access(q);
    }
    inline const void link(tree *p,tree *q)
    {
        access(p);evert(q);p->set(q,1);p->pushup();
    }
    inline tree *lca(tree *p,tree *q)
    {
        expose(p,q);
        const int dispq(q->solid_size);
        evert(root);
        access(q);const int depq(q->solid_size);
        access(p);const int depp(p->solid_size);
        int deplca(depp+depq-dispq+1>>1);
        while (p->pushdown(),1)
            if (deplca<=p->son[0]->solid_size)p=p->son[0];
            else if (!(deplca-=p->son[0]->solid_size+1))return p;
                else p=p->son[1];
    }
    inline const int path_sum(tree *p,tree *q)
    {
        expose(p,q);
        const int sum(q->solid_sum);
        evert(root);
        return sum;
    }
    inline const int subtree_sum(tree *p)
    {
        access(p);return p->val^p->dashed_sum;
    }
}using namespace Sleator_Tarjan_Trees;
int n,m,q,ans,sum[N],all;
int head[N],edc,to[N<<1],next[N<<1];
inline const void connect(const int &u,const int &v)
{
    next[++edc]=head[u];to[head[u]=edc]=v;
    next[++edc]=head[v];to[head[v]=edc]=u;
}
inline const void dfs(const int &p,const int &fa)
{
    sum[p]=node(p)->val;
    for (int son,i(head[p]);i;i=next[i])
        if ((son=to[i])^fa)
            dfs(son,p),
            sum[p]^=sum[son],
            link(node(p),node(son));
    ans^=sum[p];
    node(p)->pushup();
}
inline const void modify(const int &x,const int &y)
{
    access(node(x));
    const int dep(node(x)->solid_size);
    if (dep&1)ans^=node(x)->val^y;
    all^=node(x)->val^y;
    node(x)->val=y;
    node(x)->pushup();
}
inline const void makeroot(const int &x)
{
    access(node(x));
    const int dep(node(x)->solid_size);
    if (!(dep&1))ans^=all;
    (root=node(x))->reverse();
}
int main()
{
    read(n);read(m);read(q);
    node0=new tree[n+1];
    for (int i(1);i<=n;i++)read(node(i)->val),all^=node(i)->val;
    for (int u,v,i(1);i<n;i++)read(u),read(v),connect(u,v);
    dfs(1,0);root=node(1);
    for (int opt,x,y,i(1);i<=m+q;i++)
        switch (read(opt),read(x),opt)
        {
            case 1:makeroot(x);printf("%d\n",ans);break;
            case 2:read(y);modify(x,y);break;
            case 3:read(y);printf("%d\n",lca(node(x),node(y))-node0);break;
            case 4:read(y);printf("%d\n",path_sum(node(x),node(y)));break;
            case 5:printf("%d\n",subtree_sum(node(x)));break;
        }
    return 0;
}