题解：P5773 [JSOI2016] 轻重路径

_AyachiNene · 2025-02-18 11:17:55 · 题解

不用脑子的纯数据结构做法。

思路：

考虑把一次删点作为一次链修改，动态维护重链。首先容易发现的是，一次修改最多改变 \log n 个点的重儿子，构造方法和树剖类似，每个点的重儿子和轻儿子大小相同，这样最多改 \log n 个。再考虑如何找出要修改的点，一个想法是维护每个点重儿子大小减轻儿子大小，把这个作为每个点的权值，每次把权值等于 -1 的点找出来改了就行了。按照这个维护方法，一次修改就是把一条重链的权值减 1，轻儿子加 1。但是每次改变了重链，最初的用于修改的重链和实际的是不一样的。边权转点权，考虑用 0/1 记下每个点是否是重链，每次就是把每段 0 和每段 1 分别做区间加。先说一个细节，重链是记在儿子上的，改的是父亲，要注意开闭区间，单独处理链底和链顶的父亲。显然轻链只有 \log n 个，直接 dfs 找出来改就行了。到目前为止，用树剖或者全局平衡二叉树可以 O(n\log^2 n) 做了。

由于作者是奶龙，误以为 lct 是单 \log 并误以为很好写，去写了一大坨 lct，这里讲下细节给想吃的人。最重要的一个是 splay 和线段树结构不一样，用线段树去改轻链时，重链也是可以区间加直接改的，但 splay 不行，有的点是重链但他儿子里有轻链，这个点只能单独改，改不了一整段，导致复杂度炸了，所以要先做全局减，在改轻儿子。还有一个细节是特殊处理链底和链顶时，是一个单点加，dfs 时不能直接改，要记下位置，之后 splay 上来再改，还有些细节写代码里了。

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO
{
    char buff[1<<21],*p1=buff,*p2=buff;
    char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
    template<typename T>void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
    template<typename T>void read_s(T &x){x="";char ch=getch();while(!(ch>='a'&&ch<='z')&&!(ch>='A'&&ch<='Z'))ch=getch();while((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){x+=ch;ch=getch();}}
    template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
    char obuf[1<<21],*p3=obuf;
    void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
    char cha[100];
    template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)cha[++top]=x%10+48,x/=10;while(top)putch(cha[top]),top--;}
    template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);putch(' ');write(args...);}
    void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
    void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
int n,m;
int e[200005][2];
int ans;
int f[200005],son[200005],dep[200005],siz[200005],dfn[200005],top[200005],cnt;
namespace Nene
{
    struct splt
    {
        int ch[2],f,tag,fmn,fmx,tp;
        int val,mn;
        int top,bot;
    }t[200005];
    inline int isroot(int p){return t[t[p].f].ch[0]!=p&&t[t[p].f].ch[1]!=p;}
    inline void update(int p)
    {
        t[p].mn=t[p].val;
        if(t[p].ch[0]) t[p].mn=min(t[p].mn,t[t[p].ch[0]].mn);
        if(t[p].ch[1]) t[p].mn=min(t[p].mn,t[t[p].ch[1]].mn);
        t[p].fmn=t[p].tp;
        if(t[p].ch[0]) t[p].fmn=min(t[p].fmn,t[t[p].ch[0]].fmn);
        if(t[p].ch[1]) t[p].fmn=min(t[p].fmn,t[t[p].ch[1]].fmn);
        t[p].fmx=max({t[p].tp,t[t[p].ch[0]].fmx,t[t[p].ch[1]].fmx});
        t[p].top=t[p].bot=p;
        if(t[p].ch[0]) t[p].top=t[t[p].ch[0]].top;
        if(t[p].ch[1]) t[p].bot=t[t[p].ch[1]].bot;
    }
    inline void push(int p,int v){t[p].tag+=v;t[p].val+=v;t[p].mn+=v;}
    inline void down(int p)
    {
        if(!t[p].tag) return;
        if(t[p].ch[0]) push(t[p].ch[0],t[p].tag);
        if(t[p].ch[1]) push(t[p].ch[1],t[p].tag);
        t[p].tag=0;
    }
    int stk[200005],top;  //注意不要把splay用的栈和记要改的点的搞混了 
    int del[200005],cnt;
    inline void rotate(int p)
    {
        int f=t[p].f,ff=t[f].f;
        int k=t[t[p].f].ch[1]==p;
        if(!isroot(f)) t[ff].ch[t[ff].ch[1]==f]=p;t[p].f=ff;
        t[f].ch[k]=t[p].ch[k^1];t[t[p].ch[k^1]].f=f;
        t[p].ch[k^1]=f;t[f].f=p;
        update(f);update(p);
    }
    inline void splay(int p)
    {
        stk[++top]=p;
        for(int i=p;!isroot(i);i=t[i].f) stk[++top]=t[i].f;
        while(top) down(stk[top--]);
        while(!isroot(p))
        {
            int f=t[p].f,ff=t[f].f;
            if(!isroot(f)) (t[f].ch[1]==p)^(t[ff].ch[1]==f)?rotate(p):rotate(f); 
            rotate(p);
        }
    }
    void print(int p)
    {
        if(!p) return;
        down(p);
        print(t[p].ch[0]);
        cout<<p<<" "<<t[p].val<<endl;
        print(t[p].ch[1]);
    }
    void change(int p) //链修改 
    {
        if(!p) return;
        down(p);    //记得下传 
        if(t[p].fmn) return/* del[++cnt]=t[p].bot,*/void();
        if(!t[p].tp) del[++cnt]=f[p],del[++cnt]=f[p];
        change(t[p].ch[0]);change(t[p].ch[1]);
        update(p);
    }
    void dfs(int p)
    {
        if(!p) return;
        down(p);   //记得下传 
        if(t[p].mn>=0) return;
        if(t[p].val==-1) del[++cnt]=p;
        dfs(t[p].ch[0]);dfs(t[p].ch[1]);
    }
    inline void access(int p)
    {
        if(!e[f[p]][0]||!e[f[p]][1]) ans-=p;  //特判一条链的最后一个点 
        int tmp=p,pre=0;
        for(pre;p;pre=p,p=t[p].f) splay(p),t[p].ch[1]=pre,update(p);
        push(pre,-1);del[++cnt]=t[pre].bot;del[++cnt]=-f[t[pre].top];
        change(pre);
        while(cnt)
        {
            int x=del[cnt--];
//          cout<<x<<endl;
            if(!x) continue;
            if(x<0) splay(-x),--t[-x].val;  //修改记得splay 
            else splay(x),++t[x].val;
            update(abs(x));
        }
        splay(pre);dfs(pre);  //跟在上面变了，记得splay回来 
        while(cnt)
        {
            int x=del[cnt--];
            splay(x);t[x].val=1;update(x);
            ans+=t[e[x][0]].tp?-e[x][0]+e[x][1]:e[x][0]-e[x][1];
            if(e[x][0]) splay(e[x][0]),t[e[x][0]].tp^=1,update(e[x][0]);  //同样的，修改记得splay 
            if(e[x][1]) splay(e[x][1]),t[e[x][1]].tp^=1,update(e[x][1]);
        }
//      splay(pre);print(pre);cout<<endl;
        e[f[tmp]][e[f[tmp]][1]==tmp]=0;  //断边，不断也无所谓，但写都写lct了你不断？ 
        splay(tmp);t[tmp].ch[0]=t[t[tmp].ch[0]].f=0;
    }
}using namespace Nene;
void dfs1(int u,int fa)
{
    f[u]=fa;dep[u]=dep[fa]+1;siz[u]=1;t[u].f=fa;
    t[u].val=1e9;
    for(int i=0;i<=1;i++)
    {
        int v=e[u][i];
        if(!v) continue;
        dfs1(v,u);siz[u]+=siz[v];
        if(siz[e[u][son[u]]]<siz[v]) son[u]=i;
    }
    if(e[u][son[u]]) t[e[u][son[u]]].tp=1,t[u].val=siz[e[u][son[u]]]-siz[e[u][son[u]^1]];
    else t[u].val=1e9;  //叶子特判 
    update(e[u][son[u]]);update(u);
    ans+=e[u][son[u]];

}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);
    for(int i=1;i<=n;i++) read(e[i][0],e[i][1]);
    dfs1(1,0);
    read(m);
    write(ans),putch('\n');
    while(m--)
    {
        int p;read(p);
        access(p);
        write(ans),putch('\n');
    }
    flush();
    return 0;
}