BZOJ3991：寻宝游戏 （LCA+dfs序+树链求并）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=400010;
int Laxt[maxn],Next[maxn],To[maxn],cost[maxn];
int in[maxn],vis[maxn],times,cnt,lg2[maxn]; 
ll st[maxn][20],dis[maxn],ans;
set<int>s;
set<int>::iterator it,pre,lat;
void add(int u,int v,int c){
    Next[++cnt]= Laxt[u];
    Laxt[u]=cnt; To[cnt]=v; cost[cnt]=c;
}
void dfs(int u,int f)
{
    in[u]=++times; st[times][0]=dis[u]; 
    for(int i=Laxt[u];i;i=Next[i]){
        if(To[i]==f) continue;
        dis[To[i]]=dis[u]+cost[i];
        dfs(To[i],u);
        st[++times][0]=dis[u];
    }
}
ll LCA(int x,int y)
{
    int t=lg2[y-x+1];
    return min(st[x][t],st[y-(1<<t)+1][t]);
}
void addset(int x)
{
    s.insert(x);
    it=s.find(x); it++; lat=it; it--;
    if(it!=s.begin()) it--,pre=it,it++,ans-=LCA(*pre,*it);
    if(lat!=s.end()) ans-=LCA(*it,*lat);
    if(it!=s.begin()&&lat!=s.end()) ans+=LCA(*pre,*lat);
}
void delset(int x)
{
    it=s.find(x); it++; lat=it; it--;
    if(it!=s.begin()) it--,pre=it,it++,ans+=LCA(*pre,*it);
    if(lat!=s.end()) ans+=LCA(*it,*lat);
    if(it!=s.begin()&&lat!=s.end()) ans-=LCA(*pre,*lat);
    s.erase(x);
}
int main()
{
    int N,M,u,v,c,i,j;
    scanf("%d%d",&N,&M);
    for(i=1;i<N;i++){
        scanf("%d%d%d",&u,&v,&c);
        add(u,v,c); add(v,u,c);
    }
    dfs(1,0);
    for(lg2[1]=0,i=2;i<=times;++i) lg2[i]=lg2[i>>1]+1;
    for(i=1;i<=lg2[times];i++)
     for(j=1;j+(1<<i)-1<=times;j++)
      st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]);
    for(i=1;i<=M;i++){
    scanf("%d",&u);
        if(!vis[u]) ans+=dis[u],addset(in[u]);
        else ans-=dis[u],delset(in[u]);
        vis[i]^=1;
        it=s.end();
        ll rt=LCA(*s.begin(),*(--it));
        printf("%lld\n",(ans-rt)*2);
    }
    return 0;
}