洛谷 4115 Qtree4——鏈分治

題目：https://www.luogu.org/problemnew/show/P4115

論文：https://wenku.baidu.com/view/1bc2e4ea172ded630b1cb602.html

重鏈剖分，分別用線段樹維護每條重鏈。線段樹葉子的信息是該點輕孩子的信息；線段樹區間的信息是考慮重鏈的一個區間以及附帶的輕孩子們的信息。

修改一個點，改它所在的重鏈的信息。祖先的每條重鏈都有一個點的 “輕孩子信息” 改變了，改一下那個位置的值，更新它的線段樹，再用該重鏈的信息作為輕孩子更新更上面的重鏈。

本題每個點要維護的是 “向下以白點為端點的最長鏈” 和 “向下以白點為端點的次長鏈” 。用可刪堆維護。

線段樹區間維護 “從左邊開始、以白點結束的最長鏈” 、 “從右邊開始、以白點結束的最長鏈” 、 “中間一條兩端點都是白點的最長鏈” 。前兩個信息是為了更新第三個信息。

每條重鏈的答案放進全局可刪堆中。

注意求 “次長鏈” 的時候，自己是先把堆頂拿出來，再看剩下的堆的堆頂。要注意再看之前先用刪除堆更新一下！

預處理的時候，自己想一個一個插入。在 pshp 的時候要用到兄弟的 fl , fr , pr , sc 等信息。所以得先把線段樹整個建出來，不能有些孩子是空的就開始 pshp 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=1e5+5,M=2e5+5,INF=1e9,Lm=-1e8;
int n,hd[N],xnt,to[M],nxt[M],w[M]; bool col[N];
int siz[N],son[M],dep[N],fa[N],fw[N],top[N];
int dis[N],dp2[N],lm[N],tot,rt[N],Ls[M],Rs[M];
int dy[N],fl[M],fr[M],mx[M],pr[M],sc[M];
priority_queue<int> q[N],dq[N],ans,dans;
int Dis(int x,int y){return dp2[y]-dp2[x];}
void frs(int x)
{while(dq[x].size()&&q[x].top()==dq[x].top())q[x].pop(), dq[x].pop();
}
void pshp(int cr)
{pr[cr]=pr[ls]; sc[cr]=sc[rs];fl[cr]=Mx(fl[ls],Dis(pr[cr],pr[rs])+fl[rs]);fr[cr]=Mx(fr[rs],Dis(sc[ls],sc[cr])+fr[ls]);mx[cr]=Mx(Dis(sc[ls],pr[rs])+fr[ls]+fl[rs],Mx(mx[ls],mx[rs]));
}
void build(int l,int r,int &cr)
{cr=++tot;fl[cr]=fr[cr]=mx[cr]=-INF;pr[cr]=dy[l]; sc[cr]=dy[r];if(l==r)return; int mid=l+r>>1;build(l,mid,ls); build(mid+1,r,rs);
}
void updt(int l,int r,int cr,int p,int k)
{if(l==r){fl[cr]=fr[cr]=dis[k]; pr[cr]=sc[cr]=k;if(!q[k].size()){ mx[cr]=-INF; return;}q[k].pop(); frs(k);//
      int d2=-INF;if(q[k].size())d2=q[k].top();if(!col[k])mx[cr]=Mx(dis[k]+d2,Mx(dis[k],d2));//col[k] not col[cr]!!else mx[cr]=dis[k]+d2;q[k].push(dis[k]);return;}int mid=l+r>>1;if(p<=mid)updt(l,mid,ls,p,k); else updt(mid+1,r,rs,p,k);pshp(cr);
}
void add(int x,int y,int z)
{to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;}
void dfs(int cr,int f)
{dep[cr]=dep[f]+1; dp2[cr]=dp2[f]+fw[cr];fa[cr]=f; siz[cr]=1;for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=f){fw[v]=w[i]; dfs(v,cr); siz[cr]+=siz[v];if(siz[v]>siz[son[cr]])son[cr]=v;}
}
int Ps(int cr){return dep[cr]-dep[top[cr]]+1;}
void dfsx(int cr,int f)
{if(son[cr])top[son[cr]]=top[cr],dfsx(son[cr],cr);for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=f&&v!=son[cr]){top[v]=v;dfsx(v,cr);if(fl[rt[v]]>Lm)q[cr].push(fl[rt[v]]+w[i]);}if(!col[cr])q[cr].push(0);if(q[cr].size())dis[cr]=q[cr].top(); else dis[cr]=-INF;int p=Ps(cr),tp=top[cr];if(p>lm[tp]){lm[tp]=p;for(int i=p,k=cr;i;i--,k=fa[k])dy[i]=k;build(1,p,rt[tp]);}updt(1,lm[tp],rt[tp],p,cr);if(tp==cr)ans.push(mx[rt[cr]]);
}
void chg(int cr)
{col[cr]=!col[cr];if(!col[cr])q[cr].push(0); else dq[cr].push(0);int x=top[cr]; frs(cr);if(q[cr].size())dis[cr]=q[cr].top(); else dis[cr]=-INF;dans.push(mx[rt[x]]);if(fa[x])dq[fa[x]].push(fl[rt[x]]+fw[x]);updt(1,lm[x],rt[x],Ps(cr),cr);ans.push(mx[rt[x]]);if(fa[x])q[fa[x]].push(fl[rt[x]]+fw[x]);while(fa[x]){cr=fa[x]; x=top[cr]; frs(cr);if(q[cr].size())dis[cr]=q[cr].top(); else dis[cr]=-INF;dans.push(mx[rt[x]]);if(fa[x])dq[fa[x]].push(fl[rt[x]]+fw[x]);updt(1,lm[x],rt[x],Ps(cr),cr);ans.push(mx[rt[x]]);if(fa[x])q[fa[x]].push(fl[rt[x]]+fw[x]);}
}
int main()
{n=rdn();for(int i=1,u,v,z;i<n;i++){u=rdn();v=rdn();z=rdn();add(u,v,z);add(v,u,z);}dfs(1,0); top[1]=1; dfsx(1,0);int Q=rdn(); char ch;int x;while(Q--){cin>>ch;if(ch=='A'){while(dans.size()&&ans.top()==dans.top())ans.pop(),dans.pop();if(ans.top()<Lm)puts("They have disappeared.");else printf("%d\n",ans.top());}else{ x=rdn(); chg(x);}}return 0;
}

?