P4115

chen_qian · 2021-02-24 10:19:18 · 题解

现在已经按照题解规范修改题解，求过。

我认真仔细的检查了每一个空格，真的麻烦管理员大大申四次蒟蒻的题解

真的太感谢管理员大大一点一点指出我的小错误，实在是太谢谢了

以下做法来自 漆子超 《分治算法在树的路径问题中的应用》

本题运用线段树和树剖和平衡树实现。

我们可以将树剖视为基于链的分治算法。所以，我们可以考虑类似点分治的算法。

假如我们现在查询到一条链。那么树上路径只会分为两种情况。

1. 经过这条链。

2. 不经过。

不经过的话直接递归即可。

那么我们现在就要处理经过的情况。

考虑对于每一条链维护一颗线段树（要动态开点，不然会炸空间）。

为了更方便描述，我们定义 d_x 表示 x 到其子树的一个白点的最长距离。 dis(i,j) 表示节点 i 到 j 的最短距离。

对于线段树上每一个节点，设其维护的区间是 [l,r]，我们考虑维护三个值。

那么我们考虑如何更新父亲节点的信息 （push_up）。

假设节点 p 的左右两个儿子分别是 ls_p,rs_p 维护区间是 [l,r] 那么就有 mid=\frac{l+r}{2}。

3. mv_p=\max\left(\max(mv_{ls_p},mv_{rs_p}),rv_{ls_p}+dis(mid,mid+1)+lv_{rs_p}\right)

即下图

那么就要考虑边界条件。

当一个节点 p 维护区间 [l,l] 时

假如其是白点：

这时，考虑到经过这个点的路径可能会往下拐。所以我们定义 d2[x] 表示 x 到其子树的一个白点的次长距离。

所以 mv_p=\max(0,\max(d_l,d_l+d2_l))。

假如其是黑点：

那么我们如何来维护次长和最长呢？

首先看如何找到。

显然，要走到某个白点，必然走到其非重儿子的节点。所以直接考虑用那些轻儿子的信息来寻找。

不难发现那些轻儿子又是一条重链的开端，要经过这个重链的开端并往下走最长的距离，那不就是维护这个链的线段树根节点的的 lv 吗？

这样所有长度都得以计算，可以用堆来维护，但是由于修改操作，我们还是要使用平衡树。

修改操作

当一个点被修改时，对于其所处链的信息直接用线段树来修改即可。

关键是在其链之外的信息受到的影响。我们可以很显然的发现，一个点被修改，只会影响其到根节点路径上的节点的信息，所以我们就一个重链，一个重链的往上跳。

注意我们在初始化堆的时候，我们自上至底是用父亲找其儿子的 lv ,现在我们儿子的 lv 改变了，要更新爸爸。所以现在爸爸的堆里删去原本的贡献。然后再修改时把新的贡献加入堆，然后取最大次大更新信息。所以我们要记录一个 last 表示修改时是从哪一条链跳上来的。

上面的思路要求我们维护一个支持删除任意值的堆，有点难以实现，所以我用了 multiset。

具体实现看代码吧。另外注意以上的 [l,r] 都是新编好后的编号，查询节点信息时记得映射回去。

代码如下：

#include<bits/stdc++.h>
#define N 100005
#define INF 0x3f3f3f3f
using namespace std;
int n,m,root[N],w[N];
int head[N],idx;
int size[N],fa[N],top[N],seg[N],rev[N],son[N],cnt,len[N],dep[N],sum;
struct edge{
    int v,next,c;
}e[2*N];
void add(int u,int v,int c){
    e[++idx].v=v;
    e[idx].next=head[u];
    head[u]=idx;
    e[idx].c=c;
}
int ls[N<<2],rs[N<<2],mv[N<<2],lv[N<<2],rv[N<<2],tot;
struct myheap{
    multiset<int,greater<int> > s;
    void insert(int v){
        s.insert(v);
    }
    void del(int v){
        multiset<int, greater<int> > :: iterator it=s.lower_bound(v);
        if(it!=s.end()) s.erase(it);
    }
    int top(){
        if(s.empty()) return -INF;
        return *s.begin();
    }
}h[N],ans;
void dfs1(int x,int f){
    fa[x]=f;
    size[x]=1;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==f) continue;
        dep[y]=dep[x]+e[i].c;
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]]) son[x]=y;
    }
}
void dfs2(int x){
    if(x==son[fa[x]]) top[x]=top[fa[x]];
    else top[x]=x;
    len[top[x]]++;//记录长度 
    seg[x]=++cnt;
    rev[cnt]=x;
    if(son[x]) dfs2(son[x]);
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].v;
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y);
    }
}
void push_up(int p,int l,int r){
    int mid=(l+r)>>1;
    lv[p]=max(lv[ls[p]],dep[rev[mid+1]]-dep[rev[l]]+lv[rs[p]]);//注意映射 
    rv[p]=max(rv[rs[p]],dep[rev[r]]-dep[rev[mid]]+rv[ls[p]]);
    mv[p]=max(max(mv[ls[p]],mv[rs[p]]),rv[ls[p]]+dep[rev[mid+1]]-dep[rev[mid]]+lv[rs[p]]);
}
void build(int p,int l,int r){
    if(l==r){
        int x=rev[l];
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].v;
            if(y==fa[x]||y==son[x]) continue;
            h[x].insert(lv[root[y]]+e[i].c);
        }
        int d1=h[x].top();
        h[x].del(d1);
        int d2=h[x].top();
        h[x].insert(d1);
        lv[p]=rv[p]=max(d1,0);
        mv[p]=max(0,max(d1,d1+d2));
        return ;
    }
    int mid=(l+r)>>1;
    if(!ls[p]) ls[p]=++tot;
    build(ls[p],l,mid);
    if(!rs[p]) rs[p]=++tot;
    build(rs[p],mid+1,r);
    push_up(p,l,r);
}
void modify(int p,int l,int r,int x,int tp){
        if(l==r){
            if(x!=tp) h[x].insert(lv[root[tp]]+dep[tp]-dep[x]);
            int d1=h[x].top();
            h[x].del(d1);
            int d2=h[x].top();
            h[x].insert(d1);
            if(w[x]){ 
                lv[p]=rv[p]=d1;
                mv[p]=d1+d2;
            } 
            else{
                lv[p]=rv[p]=max(d1,0);
                mv[p]=max(0,max(d1,d1+d2));
            }
            return;
        }
        int mid=(l+r)>>1;
        if(seg[x]<=mid) modify(ls[p],l,mid,x,tp);
        else modify(rs[p],mid+1,r,x,tp);
        push_up(p,l,r);
}
void change(int x){
    int last=x; //记录上一个top[x] 
    while(x){
        int tp=top[x];
        int p1=mv[root[tp]];
        if(fa[tp]) h[fa[tp]].del(lv[root[tp]]+dep[tp]-dep[fa[tp]]);
        modify(root[tp],seg[tp],seg[tp]+len[tp]-1,x,last);
        int p2=mv[root[tp]];
        if(p1!=p2){//修改操作 
            ans.del(p1);
            ans.insert(p2);
        }
        last=tp;
        x=fa[top[x]];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    dfs1(1,0);
    dfs2(1);
    for(int i=n;i>=1;i--){//从后往前，保证子节点的线段树更新完毕。 
        int x=rev[i];
        if(x==top[x]){
            if(!root[x]) root[x]=++tot;
            build(root[x],seg[x],seg[x]+len[x]-1);
            ans.insert(mv[root[x]]);
        }
    }
    scanf("%d",&m);
    sum=n;
    while(m--){
        string op;
        cin>>op;
        int u;
        if(op[0]=='C'){
            scanf("%d",&u);
            w[u]^=1;
            if(w[u]==0) sum++;
            else sum--;
            change(u); 
        }
        else{
            if(sum==0) puts("They have disappeared.");
            else printf("%d\n",ans.top());
        }
    }
    return 0;
}