P4332 [SHOI2014] 三叉神经树

Shui_Dream · 2023-07-28 22:38:38 · 个人记录

神题。麻痹，写了两个小时 DDP 无果，获得 40 分佳绩。似乎是假做法。

来讲讲 LCT 正解。

对于每个点，我们记录他的儿子中 1 的个数为这个点的权值，显然每个点的权值 \in [0,3]。特殊的，令点权为 x，这个点的颜色即为 \lfloor\frac{x}{2}\rfloor。

我们每次相当于修改一个节点的权值，这个点会影响他父亲的权值。加入到了一个点颜色没有改变，那么再往上的点的状态也不会改变。

所以每次修改的是一个 自底向上的链。我们可以利用 LCT 来把这个点找出来。

假设我们修改一个外界点为 0\to 1。相当于给他的父亲的权值 +1 。那么只有他的父亲权值为 1 才会改变父亲点的染色。进而这个点又会影响他的父亲。所以最后影响到的是一个自底而上的权值为 1 的链。

比如： 2\to1\to1\to1...\to1。我们改变这条链的权值变成 3\to2\to2...\to2。

我们可以在 LCT 上维护加法标记来修改。

至于怎么找到这个链最上面的点，有 2 种方法：

Splay 上二分,维护 1 的个数和总点个数在二叉树上一直跳即可。
LCT上维护信息，维护深度最大的不为 1 的点。

这里采用第二种。那么直接修改即可。

加入我们修改一个外界点为 1\to 0 相当于，把权值 -1。那么会对权值为 2 的点影响。同样的我们维护深度最大的不为 2 的点。找到一个向上的 2 的链，再加上 -1 标记即可。

具体查询：直接利用 LCT 的操作，打通一条从指定点 u 到根节点 1 的路径。再 Splay(u) 即可查询到链的顶端 v 。

若点 v 存在，则 Splay(v) 并加上加标记。
否则，说明会一直影响到根节点的信息，加上加标记并改变答案。

具体见代码。

#include<bits/stdc++.h>
#define Iv inline void
typedef long long LL;
using namespace std;
const int N=15e5;
namespace LCT{
#define ls tr[p].c[0]
#define rs tr[p].c[1]
struct node{
    int c[2],fa;
    int v,n1,n2,tg;
} tr[N+5]; 
inline bool gd(int p) { return tr[tr[p].fa].c[1]==p;}
inline bool isroot(int p) { return !tr[p].fa || tr[tr[p].fa].c[gd(p)]!=p;}
Iv cnet(int u,int d,int v){if(u) tr[u].c[d]=v; if(v) tr[v].fa=u;}
Iv addt(int p,int w){
    tr[p].v^=3; swap(tr[p].n1,tr[p].n2); tr[p].tg+=w;
}
Iv pushdn(int p) {
    if(tr[p].tg){
        if(ls) addt(ls,tr[p].tg); 
        if(rs) addt(rs,tr[p].tg); 
        tr[p].tg=0;
    }
}
Iv pushup(int p) { 
    if(!(tr[p].n1=tr[rs].n1) && !(tr[p].n1=p*(tr[p].v!=1))) tr[p].n1=tr[ls].n1;
    if(!(tr[p].n2=tr[rs].n2) && !(tr[p].n2=p*(tr[p].v!=2))) tr[p].n2=tr[ls].n2;
}
Iv pdnw(int p){
    if(!isroot(p)) pdnw(tr[p].fa);
    pushdn(p);
}
Iv rot(int p){
    int fp=tr[p].fa,gp=tr[fp].fa;
    int d=gd(p);
    if(isroot(fp)) tr[p].fa=tr[fp].fa;
    else cnet(gp,gd(fp),p);
    cnet(fp,d,tr[p].c[!d]); cnet(p,!d,fp);
    pushup(fp); pushup(p);
}
Iv splay(int p){
    pdnw(p);
    while(!isroot(p)){
        int fp=tr[p].fa;
        if(!isroot(fp)){
            if(gd(fp)==gd(p)) rot(fp);
            else rot(p);
        }
        rot(p);
    }
    pushup(p);
}
Iv access(int x){
    for(int y=0;x;x=tr[y=x].fa)
        splay(x) , tr[x].c[1]=y, pushup(x);
}
#undef ls
#undef rs
}
using namespace LCT;
int n,nm,d[N+5];
int main(){
    scanf("%d",&n); nm=3*n+1;
    for(int i=1;i<=n;i++){
        d[i]=3;
        for(int j=0,x;j<3;j++){
            scanf("%d",&x);
            tr[x].fa=i;
        }
    }
    queue<int> q;
    for(int i=n+1;i<=nm;i++) {
        scanf("%d",&tr[i].v);
        q.push(i);  tr[i].v<<=1;
    }
    while(!q.empty()){
        int u=q.front(); q.pop(); if(u<=n) pushup(u);
        tr[tr[u].fa].v+=tr[u].v/2;
        if(!--d[tr[u].fa]) q.push(tr[u].fa);
    }
    int ans=tr[1].v>>1,Q; scanf("%d",&Q);
    while(Q--){
        int x; scanf("%d",&x);
        int op=(tr[x].v^=2)-1;
        access(x=tr[x].fa); splay(x);
        int y=(~op?tr[x].n1:tr[x].n2);
        if(y){
            splay(x=y); if(tr[x].c[1]) addt(tr[x].c[1],op);
            tr[x].v+=op; pushup(x);
        }
        else addt(x,op),pushup(x),ans^=1;
        printf("%d\n",ans);
    }
    return 0;
}