[SDOI2015]寻宝游戏

小\(B\)最近正在玩一个寻宝游戏，这个游戏的地图中有\(N\)个村庄和\(N-1\)条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。

小\(B\)希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个游戏中宝物经常变化，有时某个村庄中会突然出现宝物，有时某个村庄内的宝物会突然消失，因此小\(B\)需要不断地更新数据，但是小\(B\)太懒了，不愿意自己计算，因此他向你求助。为了简化问题，我们认为最开始时所有村庄内均没有宝物。

Input

第一行，两个整数\(N、M，\)其中\(M\)为宝物的变动次数。

接下来的\(N-1\)行，每行三个整数\(x、y、z，\)表示村庄\(x、y\)之间有一条长度为\(z\)的道路。

接下来的\(M\)行，每行一个整数\(t，\)表示一个宝物变动的操作。若该操作前村庄\(t\)内没有宝物，则操作后村庄内有宝物；若该操作前村庄\(t\)内有宝物，则操作后村庄内没有宝物。

Output

\(M\)行，每行一个整数，其中第\(i\)行的整数表示第\(i\)次操作之后玩家找到所有宝物需要行走的最短路程。若只有一个村庄内有宝物，或者所有村庄内都没有宝物，则输出\(0\)。

Sample Input

4 5

1 2 30

2 3 50

2 4 60

2

3

4

2

1

Sample Output

0

100

220

220

280

思路：

先用线段树分治以时间分割操作，用树链剖分维护宝藏到根的覆盖区间（去重）的长度并染色，再减去所有宝藏\(lca\)到根的距离后\(*2\)，时间复杂度\(O(nlog^2n)\)

\(ps\):维护时直接寻找当前节点最近的染色祖先

\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)

#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
# define read read1<int>()
# define Type template<typename T>
Type inline const T read1(){
    T m=0;
    char k=getchar();
    while((‘0‘>k||k>‘9‘)&&(k!=‘-‘))k=getchar();
    const bool f=(k==‘-‘?1:0);
    if(f)k=getchar();
    while(‘0‘<=k&&k<=‘9‘)m=(m<<3)+(m<<1)+(k^48),k=getchar();
    return f?-m:m;
}
# define ll long long
# define N 100000
int s,m,now[N|1],fa[N|1],top[N|1],siz[N|1],tm[N|1];
ll h[N|1];
vector<int>G[N|1],V[N|1],tr[N<<2|1];
void add(int l,int r,int dl,int dr,int v,int d){
    if(l==dl&&r==dr){
        tr[d].push_back(v);
        return;
    }
    int mid=l+r>>1;
    if(dr<=mid)add(l,mid,dl,dr,v,d<<1);
    else if(mid<dl)add(mid+1,r,dl,dr,v,d<<1|1);
    else add(l,mid,dl,mid,v,d<<1),add(mid+1,r,mid+1,dr,v,d<<1|1);
}
void dfs1(int n,int f){
    fa[n]=f;
    siz[n]=1;
    for(int i=0;i<G[n].size();++i)
        if(G[n][i]^f)
            h[G[n][i]]=h[n]+V[n][i],dfs1(G[n][i],n),siz[n]+=siz[G[n][i]];
}
void dfs2(int n,int to){
    top[n]=to;
    int son=-1;
    for(int i=0;i<G[n].size();++i)
        if(G[n][i]^fa[n]&&(!~son||siz[G[n][i]]>siz[G[n][son]]))
            son=i;
    for(int i=0;i<G[n].size();++i)
        if(G[n][i]^fa[n])
            if(i^son)dfs2(G[n][i],G[n][i]);
            else dfs2(G[n][i],to);
}
ll ans[N|1],t;
int tot;
stack<pair<int,int> >sta[30];
void solve(int n){
    if(h[tm[top[n]]]>=h[n])return;
    int i=n;
    while(i&&!tm[top[i]])tm[top[i]]=i,i=fa[top[i]];
    sta[tot].push(make_pair(n,tm[top[i]]));
    t+=h[n]-min(h[tm[top[i]]],h[i]);
    if(i&&h[tm[top[i]]]<=h[i])tm[top[i]]=i;
    // printf("-<%d %d\n",n,tm[top[i]]);
}
int lca(int l,int r){
    while(top[l]!=top[r]){
        if(h[top[l]]>h[top[r]])swap(l,r);
        r=fa[top[r]];
    }
    return h[l]>h[r]?r:l;
}
void back(int n,int l){
    int i=n;
    while(top[i]!=top[l])tm[top[i]]=0,i=fa[top[i]];
    t-=h[n]-min(h[l],h[i]);
    tm[top[i]]=l;
    // printf("->%d %d\n",n,l);
}
void dfs(int d,int l,int r,int lc){
    for(int i=0;i<tr[d].size();++i){
        lc=lc?lca(lc,tr[d][i]):tr[d][i];
        solve(tr[d][i]);
    }
    ++tot;
    if(l==r)ans[l]=t-h[lc]<<1;
    else{
        int mid=l+r>>1;
        dfs(d<<1,l,mid,lc);
        dfs(d<<1|1,mid+1,r,lc);
    }
    --tot;
    while(!sta[tot].empty())back(sta[tot].top().first,sta[tot].top().second),sta[tot].pop();
    // printf("%d %d:%lld %d\n",l,r,t,lc);
    // for(int i=1;i<=s;++i)
    //     printf("%d ",tm[i]);
    // putchar(‘\n‘);
}
int main(){
    s=read,m=read;
    for(int i=1;i<s;++i){
        int u=read,v=read,t=read;
        G[u].push_back(v);
        V[u].push_back(t);
        G[v].push_back(u);
        V[v].push_back(t);
    }
    for(int i=1;i<=m;++i){
        int k=read;
        if(now[k]){
            add(1,m,now[k],i-1,k,1);
            now[k]=0;
        }
        else now[k]=i;
    }
    for(int i=1;i<=s;++i)
        if(now[i])
            add(1,m,now[i],m,i,1);
    dfs1(1,0);
    // cout<<fa[1]<<endl;
    dfs2(1,1);
    dfs(1,1,m,0);
    for(int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
	return 0;
}

[SDOI2015]寻宝游戏

原文：https://www.cnblogs.com/SYDevil/p/12943130.html