Qtree4

题意

Link

给定一棵树和一个点集，树有边权，可以为负，要求支持两种操作：

• 点集增删一个点
• 询问点集里距离最远的两个点，可以是同一个

数据范围 $n\le 10^5,q\le 2\times 10^5$

分析

由于边权可能是负的，所以求直径的贪心做法都是不成立的。

我们考虑 dp 每个点的子树内的最大深度，直接 dp 肯定是不行的。

第一种操作每次只会增删一个点，因此每个点出现的时刻都是一段连续的区间，且区间总个数是 $\mathcal{O}\left(n\right)$ 的。

考虑将 dp 数组放到以时间为值域的线段树上维护，每次 dp 时将线段树直接合并。

直接将区间修改的每个节点上的标记永久化，记录这个点在这段时间区间内的最大深度。

每个点维护以下三个信息：

1. $max\_ans$ ，表示这个节点的所有历史时刻的答案最大值，即 $dp$ 时子树内的直径最大值
2. $tag$ ，表示所有永久化的这个节点上的标记中的最大值，即一个点集在这段时间区间内的最大深度，$dp$ 时子树内的深度最大值
3. $pushdown\_tag$ 表示历史时刻中父链上合并过 $tag$ 的最大值，用于下传的标记

上面这些标记用于模拟 $Ans\leftarrow\max\left(Ans,f_u+f_v-2dep_u\right)$ 这个过程，每次 $pushdown$ 时 $max\_ans\leftarrow \max\left(max\_ans,tag+pushdown\_tag\right)$

每次合并两个节点 $u,v$ 时，把 $u,v$ 的每个节点在另外一棵树中对应的父链信息更新到这个节点上去。

假设此时 $mx$ 表示对应的父链信息

那么 $max\_ans\leftarrow \max\left(max\_ans,mx+tag-2dep\right)$ $pushdown\_tag\leftarrow \max\left(pushdown\_tag,mx-2dep\right)$

Code

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
constexpr int N=100010,M=4000010;
typedef long long ll;
constexpr ll inf=2e18;
struct _z{
    int c[2];
    ll mxa,tg,pdtg;
}z[M];int cnt;
void upd(int &u,int cl,int cr,int ql,int qr,ll v){
    if(!u){u=++cnt;z[u].mxa=z[u].tg=z[u].pdtg=-inf;}if(cl>=ql && cr<=qr){z[u].tg=max(z[u].tg,v);return;}
    int mid=(cl+cr)>>1;if(ql<=mid) upd(z[u].c[0],cl,mid,ql,qr,v);if(qr>mid) upd(z[u].c[1],mid+1,cr,ql,qr,v);
}
void add(int u,ll v){z[u].mxa=max(z[u].mxa,z[u].tg+v),z[u].pdtg=max(z[u].pdtg,v);}
void pd(int u){if(z[u].pdtg!=-inf){if(z[u].c[0]) add(z[u].c[0],z[u].pdtg);if(z[u].c[1]) add(z[u].c[1],z[u].pdtg);z[u].pdtg=-inf;}}
int merge(int u,int v,int cl,int cr,ll mxu,ll mxv,ll bs){
    if(!u && !v) return 0;if(!u){add(v,mxu);return v;}if(!v){add(u,mxv);return u;}
    mxu=max(mxu,bs+z[u].tg),mxv=max(mxv,bs+z[v].tg);add(u,mxv);add(v,mxu);pd(u),pd(v);
    z[u].mxa=max(z[u].mxa,z[v].mxa),z[u].tg=max(z[u].tg,z[v].tg);int mid=(cl+cr)>>1;
    z[u].c[0]=merge(z[u].c[0],z[v].c[0],cl,mid,mxu,mxv,bs);z[u].c[1]=merge(z[u].c[1],z[v].c[1],mid+1,cr,mxu,mxv,bs);return u;
}
int rt[N],m,cur[N],ct,n;ll dep[N],ans[N];
vector<pair<int,int> > es[N];
void dfs(int u,int fa){
    for(auto v:es[u]) if(v.first!=fa)
        dep[v.first]=dep[u]+v.second,dfs(v.first,u);
}
void dfs2(int u,int fa){
    for(auto v:es[u]) if(v.first!=fa)
        dfs2(v.first,u),rt[u]=merge(rt[u],rt[v.first],1,m,-inf,-inf,-2ll*dep[u]);
}
char s[5];bool nok[N];
vector<pair<int,int> > ss[N];
void solve(int u,int cl,int cr,ll curm){
    if(u) pd(u);int mid=(cl+cr)>>1;curm=max(curm,z[u].mxa);
    if(cl==cr){ans[cl]=curm;return;}solve(z[u].c[0],cl,mid,curm);solve(z[u].c[1],mid+1,cr,curm);
}
int main(){
    scanf("%d",&n);ct=n;
    for(int i=1;i<=n;++i)
        cur[i]=1;
    for(int i=1,u,v,w;i<n;++i)
        scanf("%d%d%d",&u,&v,&w),es[u].push_back(make_pair(v,w)),es[v].push_back(make_pair(u,w));
    dfs(1,0);
    int q;scanf("%d",&q);
    for(int i=1,t;i<=q;++i){
        scanf("%s",s);
        if(s[0]=='A'){++m;nok[m]=(ct==0);}
        else{
            scanf("%d",&t);
            if(cur[t]){
                --ct;if(cur[t]<=m) ss[t].push_back(make_pair(cur[t],m));
                cur[t]=0;
            }else{
                ++ct;cur[t]=m+1;
            }
        }
    }
    if(!m) return 0;
    for(int i=1;i<=n;++i){
        if(cur[i] && cur[i]<=m) ss[i].push_back(make_pair(cur[i],m));
        for(auto v:ss[i])
            upd(rt[i],1,m,v.first,v.second,dep[i]);
    }
    dfs2(1,0);
    solve(rt[1],1,m,0);
    for(int i=1;i<=m;++i){
        if(nok[i]) printf("They have disappeared.\n");
        else printf("%lld\n",ans[i]);
    }
    return 0;
}