Lvat_s Blog

类似虚树的东西

首先我们发现答案就是当前存在的点所构成的树的边权和的两倍

所以我们考虑用set维护dfs序，最后减掉一个lca(最前,最后)即可

具体为什么是这样么……你需要自己手动模拟一下

非常妙

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;

const int N=100005;
const long long INF=21000000000000ll;

int n,m,en,h[N],dep[N],pos[N],f[N],lg[N<<1],tag[N],Index,Size;
long long ans,d[N<<1][19],di[N];
set<int> St;

struct Edge{
int b,next;
long long v;
}e[N<<1];

void dfs(int u){
d[pos[u]=++Index][0]=di[u];
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(dep[v])continue;
    f[v]=u;
    di[v]=di[u]+e[i].v;
    dep[v]=dep[u]+1;
    dfs(v);
    d[++Index][0]=di[u];
}
}

template<typename T>inline void Read(T &x){char ch;while((ch=getchar())<'0'||ch>'9');x=ch-'0';while((ch=getchar())>='0'&&ch<='9')x=x*10+ch-'0';}
void AddEdge(int sa,int sb,long long sc){e[++en].b=sb;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}
set<int>::iterator Pre(const set<int>::iterator &x){set<int>::iterator Tx=x;return --Tx;}
set<int>::iterator Nxt(const set<int>::iterator &x){set<int>::iterator Tx=x;return ++Tx;}
long long Mn(int u,int v){int w=lg[v-u+1];return min(d[u][w],d[v-(1<<w)+1][w]);}
long long Dist(){if(!Size)return 0ll;int u=*St.begin(),v=*Pre(St.end());return Mn(u,v);}

void Ins(int x){
ans+=d[x][0];
St.insert(x);
Size++;
if(Size==1)return;
set<int>::iterator Tx=St.find(x);
if(Tx==St.begin()){ans-=Mn(*Tx,*Nxt(Tx));return;}
if(Nxt(Tx)==St.end()){ans-=Mn(*Pre(Tx),*Tx);return;}
ans+=Mn(*Pre(Tx),*Nxt(Tx))-Mn(*Tx,*Nxt(Tx))-Mn(*Pre(Tx),*Tx);
}

void Del(int x){
ans-=d[x][0];
if(Size==1){St.erase(x);Size--;return;}
set<int>::iterator Tx=St.find(x);
if(Tx==St.begin()){ans+=Mn(*Tx,*Nxt(Tx));St.erase(x);Size--;return;}
if(Nxt(Tx)==St.end()){ans+=Mn(*Pre(Tx),*Tx);St.erase(x);Size--;return;}
ans-=Mn(*Pre(Tx),*Nxt(Tx))-Mn(*Tx,*Nxt(Tx))-Mn(*Pre(Tx),*Tx);
St.erase(x);
Size--;
}

int main(){
freopen("3991.in","r",stdin);
freopen("3991.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<n;i++){
    int u,v;
    long long w;
    Read(u);Read(v);Read(w);
    AddEdge(u,v,w);
	AddEdge(v,u,w);
}
dfs(1);
for(int i=2;i<=Index;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=lg[Index];i++)for(int j=1;j+(1<<i)-1<=Index;j++)d[j][i]=min(d[j][i-1],d[j+(1<<i-1)][i-1]);
for(int i=1;i<=m;i++){
    int x;
    Read(x);
    tag[x]^=1;
    if(tag[x])Ins(pos[x]);
    else Del(pos[x]);
    printf("%lld\n",ans-Dist()<<1);
}
return 0;
}