LCT 维护树上信息合并

· · 题解

众所周知，本题的代码可以不到 2k，那些场上迅速过了的大多都预存了模板，我也不是说这样不行，不过即使不预存模板也能首 A，因为有一个能常数之外偏序掉树剖的数据结构：Link-Cut-Tree！

首先本题的信息具有结合律，可以看作一种矩阵，鱼框的状态只有五种，我们将一条链的信息看作从鱼框的每一种状态开始，经过这条链之后会变成什么状态，吃下了几条阴阳鱼，实现时可以将末三位表示状态：

struct dat{
    int p[5];//0,10,20,11,21;
    dat operator*(const dat &z)const{
        return{
            ((p[0]>>3)<<3)+z.p[p[0]&7],
            ((p[1]>>3)<<3)+z.p[p[1]&7],
            ((p[2]>>3)<<3)+z.p[p[2]&7],
            ((p[3]>>3)<<3)+z.p[p[3]&7],
            ((p[4]>>3)<<3)+z.p[p[4]&7]
        };
    }
    void init(int d){
        if(d)*this={3,8,9,4,4};
        else *this={1,2,2,8,11};
    }
    void init(){*this={0,1,2,3,4};}
    void put(){
        for(int i=0;i<5;++i)
            printf("%d%c",p[i]," \n"[i==4]);
    }
}

而每次询问的初始状态都是 0，即鱼框里没有鱼，所以将链上的信息合并之后的 p_0 除去末三位就是答案。

为了实现方便需要换根，可以将正的和反的信息都存下来，翻转时交换即可。

于是代码很好写：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct dat{
    int p[5];//0,10,20,11,21;
    dat operator*(const dat &z)const{
        return{
            ((p[0]>>3)<<3)+z.p[p[0]&7],
            ((p[1]>>3)<<3)+z.p[p[1]&7],
            ((p[2]>>3)<<3)+z.p[p[2]&7],
            ((p[3]>>3)<<3)+z.p[p[3]&7],
            ((p[4]>>3)<<3)+z.p[p[4]&7]
        };
    }
    void init(int d){
        if(d)*this={3,8,9,4,4};
        else *this={1,2,2,8,11};
    }
    void init(){*this={0,1,2,3,4};}
    void put(){
        for(int i=0;i<5;++i)
            printf("%d%c",p[i]," \n"[i==4]);
    }
}s1[N],s2[N],v[N];
int n,q,cl[N],rv[N],t[N][2],f[N];
#define ls t[x][0]
#define rs t[x][1]
#define tp(x) (t[f[x]][1]==x)
#define in(x) (t[f[x]][0]==x||tp(x))
void pp(int x){
    s1[x]=s2[x]=v[x];
    if(ls)s1[x]=s1[ls]*s1[x],s2[x]=s2[x]*s2[ls];
    if(rs)s1[x]=s1[x]*s1[rs],s2[x]=s2[rs]*s2[x];
}
void rev(int x){
    rv[x]^=1,swap(ls,rs);
    swap(s1[x],s2[x]);
}
void pd(int x){
    if(rv[x]){
        if(ls)rev(ls);
        if(rs)rev(rs);rv[x]=0;
    }
}
void ppd(int x){
    if(in(x))ppd(f[x]);pd(x);
}
void rot(int x){
    int y=f[x],k=tp(x),w=t[x][!k];
    t[f[w]=t[x][!k]=y][k]=w;
    if(in(y))t[f[y]][tp(y)]=x;
    f[x]=f[y],f[y]=x,pp(y);
}
void splay(int x){
    ppd(x);
    for(int y=f[x];in(x);rot(x),y=f[x])
        if(in(y))rot(tp(x)^tp(y)?x:y);pp(x);
}
void acs(int x){
    for(int y=0;x;x=f[y=x])
        splay(x),rs=y,pp(x);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    int i,j,k,l,r,x,y;
    for(x=1;x<=n;++x)cin>>cl[x],v[x].init(cl[x]),pp(x);
    for(i=1;i<n;++i){
        cin>>x>>y;
        acs(x),splay(x),rev(x),f[x]=y;
    }
    s1[0].init(),s1[0].init();
    while(q--){
        cin>>k>>x;
        if(k==1)splay(x),v[x].init(cl[x]^=1),pp(x);
        else{
            cin>>y,acs(x),splay(x),rev(x);
            acs(y),splay(x);
            printf("%d\n",s1[x].p[0]>>3);
        }
    }return 0;
}