题目大意：支持多次操作，增加或删除一个关键点
动态维护虚树边权和*2
分析：可以用树链求并的方法，最后减去虚树的根到1距离
注意到树链求并是所有点到根距离-所有dfn序相邻两点的LCA到根距离
找dfn左右两个点稍微求一下，那就平衡树维护咯
树总根是dfn最小的点和最大的点的LCA
=================================================
md智障想偷懒不写平衡树，写了个set，然后gg不会写搞了两个小时
=================================================
set定义+迭代器
set<int>S;
set<int>::iterator it;set存储方式：
1.左闭右开
begin()是指向第一个点,end()指向最后一个点后的一个结束指针
2.特别的，set空时begin()==end()
3.不允许有重复元素
set小函数（方便使用）
int getnxt(int x){
it=S.upper_bound(x);
return it!=S.end() ? pid[*it] : -1;
}
int getpre(int x){
it=S.lower_bound(x);
return it!=S.begin() ? pid[*(--it)] : -1;
}
int getfirst(){
it=S.begin();
return it!=S.end() ? pid[*it] : -1;
}
int getlast(){
it=S.end();
return it!=S.begin() ? pid[*(--it)] : -1;
} 本题代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <set>
using namespace std;
typedef long long LL;
const int M=100007;
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=0;
for(;isdigit(c);c=getchar())x=x*10+c-48;
return f?x:-x;
}
int vis[M];
int n,m;
bool use[M];
int g[M],te;
struct edge{int y,next;LL d;}e[M<<1];
void addedge(int x,int y,LL d){
e[++te].y=y;e[te].d=d;e[te].next=g[x];g[x]=te;
}
int dfn[M],pid[M],tdfn;
int a[M<<1][20],ln[M<<1],pos[M],T;
LL dis[M];
void dfs(int x,int fa){
pid[dfn[x]=++tdfn]=x;
a[pos[x]=++T][0]=x;
int p,y;
for(p=g[x];p;p=e[p].next)
if((y=e[p].y)!=fa){
dis[y]=dis[x]+e[p].d;
dfs(y,x);
a[++T][0]=x;
}
}
set<int>S;
set<int>::iterator it;
int mn(int x,int y){return dfn[x]<dfn[y]?x:y;}
void init(){
int i,j,l;
for(i=2;i<=T;i++) ln[i]=ln[i>>1]+1;
for(i=T;i>0;i--){
l=ln[T-i+1];
for(j=1;j<=l;j++) a[i][j]=mn(a[i][j-1],a[i+(1<<j-1)][j-1]);
}
}
int LCA(int x,int y){
x=pos[x],y=pos[y];
int l=ln[y-x+1];
return mn(a[x][l],a[y-(1<<l)+1][l]);
}
int getnxt(int x){
it=S.upper_bound(x);
return it!=S.end() ? pid[*it] : -1;
}
int getpre(int x){
it=S.lower_bound(x);
return it!=S.begin() ? pid[*(--it)] : -1;
}
int getfirst(){
it=S.begin();
return it!=S.end() ? pid[*it] : -1;
}
int getlast(){
it=S.end();
return it!=S.begin() ? pid[*(--it)] : -1;
}
int main(){
freopen("a.txt","r",stdin);
int i,x,y,z,l,r;
LL ans=0;
n=rd(),m=rd();
for(i=1;i<n;i++){
x=rd(),y=rd(),z=rd();
addedge(x,y,z);
addedge(y,x,z);
}
dfs(1,0);
init();
for(i=1;i<=m;i++){
x=rd();
if(use[x]){
S.erase(dfn[x]);
l=getpre(dfn[x]);
r=getnxt(dfn[x]);
if(l!=-1&&r!=-1) ans-=dis[LCA(l,r)];
if(l!=-1) ans+=dis[LCA(l,x)];
if(r!=-1) ans+=dis[LCA(x,r)];
ans-=dis[x];
}
else{
l=getpre(dfn[x]);
r=getnxt(dfn[x]);
S.insert(dfn[x]);
if(l!=-1&&r!=-1) ans+=dis[LCA(l,r)];
if(l!=-1) ans-=dis[LCA(l,x)];
if(r!=-1) ans-=dis[LCA(x,r)];
ans+=dis[x];
}
use[x]^=1;
it=S.begin();
if(it==S.end()) puts("");
else{
l=getfirst();
r=getlast();
printf("%lld\n",(ans-dis[LCA(l,r)])*2);
}
}
return 0;
}