Luogu3320[SDOI2015]寻宝游戏

题面：洛谷

解析

树链的并，考虑用(set)维护新插入的节点的(dfs)序的前驱与后继，然后维护树链长度，再减去一段从某点到(root)的距离即可，那么这个点是什么呢？画图手玩发现可以用(set)中(dfs)序最小的点与(dfs)序最大的点的(lca)表示，注意答案要乘2。

ps:还是说一下树链的并吧，其实就是给定若干个点，求它们到(root)的链的并的长度。

考虑对这些点按(dfs)序排序，那么有：

[ans=sum_{i=1}^{n} dep[p[i]]-sum_{i=1}^{n-1} dep[lca(p[i],p[i+1])] ]

代码


// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
const LL INF=1e18; const int nlog=17;
int n,m,teature[N];
#define gc() getchar()
inline int In(){
    char c=gc(); int x=0,ft=1;
    for(;c<'0'||c>'9';c=gc()) if(c=='-') ft=-1;
    for(;c>='0'&&c<='9';c=gc()) x=x*10+c-'0';
    return x*ft;
}
int h[N],e_tot=0;
struct E{ int to,nex,d; }e[N<<1];
inline void add(int u,int v,int w){
    e[++e_tot]=(E){v,h[u],w}; h[u]=e_tot;
}
int dfs_clock=0,q_cnt=0,dfn[N],rk[N];
int id[N],p[N<<1][nlog+5],power[nlog+5];
LL d[N],ans=0;
void dfs(int u,int pre,LL dep){
    dfn[u]=++dfs_clock; rk[dfs_clock]=u;
    d[u]=dep; p[++q_cnt][0]=u; id[u]=q_cnt;
    for(int i=h[u],v;i;i=e[i].nex){
        v=e[i].to; if(v==pre) continue;
        dfs(v,u,dep+e[i].d); p[++q_cnt][0]=u;
    }
}
inline void get_st(){
    power[0]=1; for(int i=1;i<=nlog;++i) power[i]=power[i-1]*2;
    for(int j=1;j<=nlog;++j){
        for(int i=1;i+power[j]<=q_cnt;++i){
            if(d[p[i][j-1]]<d[p[i+power[j-1]][j-1]]) p[i][j]=p[i][j-1];
            else p[i][j]=p[i+power[j-1]][j-1];
        }
    }
}
inline int LCA(int x,int y){
    if(id[x]<id[y]) swap(x,y); int k=log(id[x]-id[y]+1)/log(2);
    return d[p[id[y]][k]]<d[p[id[x]-power[k]+1][k]]?p[id[y]][k]:p[id[x]-power[k]+1][k];
}
set<int> Set;
set<int> :: iterator it;
inline void Modify(int p,int op){
    ans=ans+1ll*op*d[p]; int u=-1,v=-1;
    if(Set.empty()){ Set.insert(dfn[p]); return; }
    it=Set.lower_bound(dfn[p]);
    if(it!=Set.begin()) u=rk[*--it];
    it=Set.upper_bound(dfn[p]);
    if(it!=Set.end()) v=rk[*it];
    if(u!=-1&&v!=-1) ans=ans+1ll*op*d[LCA(u,v)];
    if(u!=-1) ans=ans-1ll*op*d[LCA(u,p)];
    if(v!=-1) ans=ans-1ll*op*d[LCA(v,p)];
    if(op==1) Set.insert(dfn[p]);
    else Set.erase(dfn[p]);
}
int main(){
    n=In(); m=In();
    for(int i=1,u,v,w;i<n;++i){
        u=In(); v=In(); w=In();
        add(u,v,w); add(v,u,w);
    }
    dfs(1,-1,0); get_st();
    for(int i=1;i<=n;++i) teature[i]=1;
    for(int i=1,t;i<=m;++i){
        t=In(); Modify(t,teature[t]);
        teature[t]=-teature[t];
        int pre=LCA(rk[*Set.begin()],rk[*--Set.end()]);
        printf("%lld
",2ll*(ans-d[pre]));
    }
    return 0;
}