黈黈黈告訴我們， 該題即求包含所有點的最小聯通子圖的邊權和的兩倍。 黈黈黈告訴我們， 處理出樹的dfs序，把點按DFS序從小到大排列成環後環上所有相鄰點的距離和。 黈黈黈告訴我們， 這可以用set處理。 然後就做完了。 代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<set>
using namespace std;
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define LL long long
#define DB double
#define mkp(x,y) make_pair(x,y)
#define pii pair<int,int>
#define X first
#define Y second
#define cl T[num].lc
#define cr T[num].rc
const int N=100005;
int n,m;LL ans;
int he[N],ne[N<<1],to[N<<1],W[N<<1],tot;
int dad[N],dfn[N],nfd[N],cnt,sz[N],son[N],pre[N];LL dep[N];
set<int>st;
void add(int x,int y,int z){
ne[++tot]=he[x];W[tot]=z;to[tot]=y;he[x]=tot;
}
void DFS1(int x){
int i,y;sz[x]=1;
for(i=he[x];i;i=ne[i])if((y=to[i])!=pre[x]){
dep[y]=dep[x]+W[i];
pre[y]=x;
DFS1(y);
if(sz[y]>sz[son[x]])son[x]=y;
sz[x]+=sz[y];
}
}
void DFS2(int x){
int i,y;
dad[x]=son[pre[x]]==x?dad[pre[x]]:x;
nfd[dfn[x]=++cnt]=x;;
if(son[x])DFS2(son[x]);
for(i=he[x];i;i=ne[i])if((y=to[i])!=pre[x]&&y!=son[x])
DFS2(y);
}
int lca(int x,int y){
int fx=dad[x],fy=dad[y];
while(fx!=fy){
if(dep[fx]>dep[fy])fx=dad[x=pre[fx]];
else fy=dad[y=pre[fy]];
}
return dep[x]>dep[y]?y:x;
}
LL dis(int x,int y){
return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
}
int main(){
int i,x,y,z;
set<int>::iterator ii,jj,kk,ll,rr;
scanf("%d%d",&n,&m);tot=1;
rep(i,2,n){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
DFS1(1);DFS2(1);
ll=st.insert(0).X;rr=st.insert(n+1).X;
while(m--){
scanf("%d",&x);
ii=st.lower_bound(dfn[x]);
if(*ii==dfn[x]){
jj=kk=ii;++jj;--kk;
st.erase(ii);
if(st.size()<4){
ans=0;puts("0");continue;
}
if(jj==rr){jj=ll;++jj;}
if(kk==ll){kk=rr;--kk;}
y=nfd[*jj];z=nfd[*kk];
ans-=dis(x,y)+dis(x,z)-dis(y,z);
}
else{
ii=st.insert(dfn[x]).X;
jj=kk=ii;++jj;--kk;
if(st.size()<4){
puts("0");continue;
}
if(jj==rr){jj=ll;++jj;}
if(kk==ll){kk=rr;--kk;}
y=nfd[*jj];z=nfd[*kk];
ans+=dis(x,y)+dis(x,z)-dis(y,z);
}
printf("%lld\n",ans);
}
return 0;
}