「SHOI2014」三叉神经树（加强版）题解

非加强版链接

题意：

给定一棵有 $3n+1$ 个结点的有根树，其中有 $n$ 个实点和 $2n+1$ 个虚点，每个实点有 $3$ 个儿子而所有虚点都没有儿子。实点从 $1$ 到 $n$ 编号，虚点从 $n+1$ 到 $3n+1$ 编号，且 $1$ 号点为根。

每个点都有一个点权，其中，虚点的点权由输入确定且只可能为 $0$ 或 $1$，而实点的点权为三个子结点的点权的众数。你需要支持三种操作（操作总数为 $m$）：

• 操作 $1$：输入 $1\ z$，表示将虛点 $z$ 的新点权设为其原点权异或 $1$ 后的值。
• 操作 $2$：输入 $2\ x\ y$，表示给定两实点 $x,y$，若 $x,y$ 不同且不为祖孙关系则将 $x$ 的父结点与 $y$ 的父结点交换。
• 操作 $3$：输入 $3\ x$，表示查询实点 $x$ 的点权。

题解：

我校大佬LinZhengyu对于原题可以让树剖过非常生气，于是他加强了这道题，把树剖卡掉了 （毒瘤啊）。

考虑使用 $LCT$ 实现这些功能 ，想用树剖？你是想要被嬴政弃市吗？ 。

操作 $1$：

这是非加强版就有的操作。

首先显然有：每一次修改权值改变的点的集合一定是某一条自上而下的链，并且不一定是从根开始的，但是一定以被修改点结尾的。

我们定义 $sum_i$为 $i$ 号节点的子节点的点权和。

我们发现：

• 若修改的点是从 $1$ 变成 $0$，那么从修改点一直往上，只有 $sum=2$ 的点的点权会改变（从 $1$ 变成 $0$）
• 若修改的点是从 $0$ 变成 $1$，那么从修改点一直往上，只有 $sum=1$ 的点的点权会改变（从 $0$ 变成 $1$）

那么我们修改一个点，要找到的就是深度最大且 $sum\ne 1/2$ 的点。

这个可以二分求得，但是这样会多一个 $\log$ （然后你就被毒瘤出题人卡了），我们考虑直接维护。我们记 $t1_i,t2_i$ 为从 $i$ 号点往上，深度最大且 $sum\ne 1/2$ 的点，然后我们只需要在 $pushup$ 中魔改即可，具体细节如下：
以维护 $t1_x$ 为例（$t2_x$ 同理）：我们先从其中的一个儿子转移上来，比如说 $ch_{x,0}$，如果这时 $t1_x$ 还是没有值，我们就考虑 $x$ 点本身，如果符合要求，那么 $t1_x=x$，否则 $t1_x=t1_{ch_{x,1}}$。

这之后就是修改一条链的操作了，直接套模板。

细节方面：

设当前被修改点为 $x$。

• 在修改的时候，不能将被修改的叶子节点也放到 $splay$ 当中（即 $access$ 的时候一定要从 $fa_x$ 开始 $access$），因为如果叶子节点的 $sum$ 为 $0$，那么这个 $splay$ 里面的 $t1_x,t2_x$ 都是这个叶子节点，那么我们维护就没有意义了。
• 在把 $fa_x$ 旋根之后，一定是修改右子树，而不是修改整个子树，因为左子树的信息并不会改变。
• 在修改了右子树之后，不要忘记对 $fa_x$ 进行单点修改。

单次操作时间复杂度为 $O(\log{n})$。

操作 $2$：

这是 毒瘤 出题人为了卡树剖而加的操作。

但其实这个操作在我们会了操作 $1$ 后是没有什么难度的。显然，如果 $x,y$ 的点权相等，可以直接用 $link$ 个 $cut$ 操作解决；如果不相等，那么就是先修改这两个点（与操作 $1$ 不同的是，这次修改不改变实际点权，只是假装这个点被修改了，以此来影响祖先），然后再换父亲。单次操作时间复杂度为 $O(\log{n})$。

操作 $3$：

这就是一个查询操作，显然直接把 $x\ splay$ 上去，就可以直接查询了,单次操作时间复杂度为 $O(\log{n})$。

综上所述，我们成功用 $LCT$ 解决了这道题，时间复杂度为 $O(m\log{n})$，空间复杂度为 $O(n)$ ，把树剖吊起来打。

Code：

#include <stdio.h>
#include <algorithm>
#define il inline
#define N 900002
using namespace std;

int n,q,to[N],nx[N],head[N],sze,st[N],f[N];
int F[N],s[N][2],lz[N],t1[N],t2[N],val[N],sum[N];

il void add(int u,int v){to[++sze]=v,nx[sze]=head[u],head[u]=sze;}

il void dfs(int u)
{
    int i,v;
    for (i=head[u]; i; i=nx[i]) dfs(v=to[i]),sum[u]+=val[v];
    if (u<=n) val[u]=sum[u]>1;
}

il int ckrt(int x){return s[F[x]][0]==x||s[F[x]][1]==x;}

il void tag(int x,int v){if (x) val[x]=(sum[x]+=v)>1,swap(t1[x],t2[x]),lz[x]+=v;}

il void pushup(int x)
{
    t1[x]=t1[s[x][1]],t2[x]=t2[s[x][1]];
    if (!t1[x])
    {
        if (sum[x]!=1) t1[x]=x;
        else t1[x]=t1[s[x][0]];
    }
    if (!t2[x])
    {
        if (sum[x]!=2) t2[x]=x;
        else t2[x]=t2[s[x][0]];
    }
}

il void pushdown(int x)
{
    if (!lz[x]) return;
    tag(s[x][0],lz[x]),tag(s[x][1],lz[x]),lz[x]=0;
}

il void rot(int x)
{
    int y=F[x],z=F[y],k=(s[y][1]==x),w=s[x][!k];
    if (ckrt(y)) s[z][s[z][1]==y]=x;
    s[x][!k]=y,s[y][k]=w;
    if (w) F[w]=y;
    F[F[y]=x]=z,pushup(y);
}

il void splay(int x)
{
    int y,z=0;
    for (st[++z]=y=x; ckrt(y); st[++z]=y=F[y]);
    while (z) pushdown(st[z--]);
    while (ckrt(x))
    {
        z=F[y=F[x]];
        if (ckrt(y)) (s[z][0]==y)^(s[y][0]==x)?rot(x):rot(y);
        rot(x);
    }
    pushup(x);
}

il void access(int x){for (int y=0; x; x=F[y=x]) splay(x),s[x][1]=y,pushup(x);}

il int check(int x,int y)
{
    if (x==y) return 0;
    access(x),splay(x),splay(y);
    if (s[y][1]==x||s[s[y][1]][1]==x) return 0;
    access(y),splay(y),splay(x);
    if (s[x][1]==y||s[s[x][1]][1]==y) return 0;
    return 1;
}

il void upt(int w,int o)
{
    int x=f[w],y,z;
    access(x),splay(x);
    if (val[w]) y=t2[x],z=-1;
    else y=t1[x],z=1;
    if (y)
        splay(y),tag(s[y][1],z),pushup(s[y][1]),
	sum[y]+=z,val[y]=sum[y]>1,pushup(y);
    else tag(x,z),pushup(x);
    if (!o) val[w]^=1;
}

int main()
{
    scanf("%d",&n); int i,x,y,z,w;
    for (i=1; i<=n; i++)
	scanf("%d%d%d",&x,&y,&z),
	f[x]=f[y]=f[z]=F[x]=F[y]=F[z]=i,
	add(i,x),add(i,y),add(i,z);
    for (i=n+1; i<3*n+2; i++) scanf("%d",val+i);
    dfs(1);
	
    for (scanf("%d",&q); q; q--)
    {
        scanf("%d%d",&i,&x);
        if (i==1) upt(x,0);
        if (i==2)
        {
            scanf("%d",&y);
            if (!check(x,y)) continue;
            z=f[x],w=f[y];
            if (val[x]==val[y]) access(z),splay(x),access(w),splay(y);
            else upt(x,1),upt(y,1),splay(x),splay(y);
            f[x]=F[x]=w,f[y]=F[y]=z;
        }
        if (i==3) splay(x),printf("%d\n",val[x]);
    }
	
    return 0;
}