惨啊，一开始打了个虚树模板，后来才发现居然是dfs+set
幸好树剖求LCA没有白写QWQ

#include<stdio.h>
#include<string.h>
#include<set>
#include<algorithm>
#define N 100010
typedef long long L;
using namespace std;
struct E{ int v,c,nt; } G[N<<1]; set<int> s;
int f[N],sz[N],son[N],h[N]={0},d[N]={0},t[N]={0};
int dfn[N],cnt=0,d_cl=0,n,m,r[N];
L dis[N],ans=0ll; bool v[N]={0};
inline void adj(int a,int b,int c){
    G[++cnt]=(E){b,c,h[a]}; h[a]=cnt;
    G[++cnt]=(E){a,c,h[b]}; h[b]=cnt;
}
void dijk(int x,int p){
    f[x]=p; d[x]=d[p]+1; son[x]=0; sz[x]=1;
    for(int v,i=h[x];i;i=G[i].nt){
        if((v=G[i].v)==p) continue;
        dis[v]=dis[x]+G[i].c; dijk(v,x);
        sz[x]+=sz[v];
        if(sz[v]>sz[son[x]]) son[x]=v;
    }
}
void spfa(int x,int p){
    t[x]=p; r[dfn[x]=++d_cl]=x;
    if(son[x]) spfa(son[x],p);
    for(int v,i=h[x];i;i=G[i].nt)
        if((v=G[i].v)!=f[x]&&v!=son[x]) spfa(v,v);
}
int dx(int x,int y){
    while(t[x]!=t[y]) 
        if(d[t[x]]>d[t[y]]) x=f[t[x]];else y=f[t[y]];
    return d[x]<d[y]?x:y;
}
long long dist(int x,int y){
    return dis[x]+dis[y]-2*dis[dx(x,y)];
}
void in(int x){
    s.insert(dfn[x]);
    set<int>::iterator it;
    it=s.find(dfn[x]); 
    int a=(it==s.begin()?0:r[*--it]);
    it=s.find(dfn[x]); 
    int b=(++it==s.end()?0:r[*it]);
    if(a) ans+=dist(a,x);
    if(b) ans+=dist(x,b);
    if(a&&b) ans-=dist(a,b);
}
void del(int x){
    set<int>::iterator it;
    it=s.find(dfn[x]); 
    int a=(it==s.begin()?0:r[*--it]);
    it=s.find(dfn[x]); 
    int b=(++it==s.end()?0:r[*it]);
    if(a) ans-=dist(a,x);
    if(b) ans-=dist(x,b);
    if(a&&b) ans+=dist(a,b);
    s.erase(dfn[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int a,b,c,i=1;i<n;++i) 
        scanf("%d%d%d",&a,&b,&c),adj(a,b,c);
    dijk(1,0); spfa(1,1);
    for(int x,i=0;i<m;++i){
        scanf("%d",&x);
        if(v[x]) del(x); else in(x); v[x]^=1;
        printf("%lld\n",s.size()?ans+dist(r[*s.begin()],r[*--s.end()]):0);
    }
}

用 STL 自带的 set 容器维护起来很方便。你也可以手写树状数组/线段树/平衡树。

#include <cstdio>
#include <set>

typedef long long LL;
const int MN = 100005;

int N, M;
int h[MN], nxt[MN * 2], to[MN * 2], w[MN * 2], tot;
inline void ins(int x, int y, int z) {
nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot;
}

int dfn[MN], idf[MN], dfc;
int dep[MN], faz[MN][17];
LL dis[MN];

void DFS(int u, int fz) {
dfn[u] = ++dfc; idf[dfc] = u; dep[u] = dep[faz[u][0] = fz] + 1;
for (int j = 1; 1 << j < dep[u]; ++j) faz[u][j] = faz[faz[u][j - 1]][j - 1];
for (int i = h[u]; i; i = nxt[i]) if (to[i] != fz) dis[to[i]] = dis[u] + w[i], DFS(to[i], u);
}

inline int lca(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
for (int d = dep[x] - dep[y], j = 0; d; d >>= 1, ++j)
if (d & 1) x = faz[x][j];
if (x == y) return x;
for (int j = 16; ~j; --j) if (faz[x][j] != faz[y][j])
x = faz[x][j], y = faz[y][j];
return faz[x][0];
}

inline LL dist(int x, int y) { return dis[x] + dis[y] - 2 * dis[lca(x, y)]; }

bool vis[MN];
std::set<int> st;
std::set<int>::iterator it;
LL Ans;

int main() {
scanf("%d%d", &N, &M);
for (int i = 1, x, y, z; i < N; ++i) {
scanf("%d%d%d", &x, &y, &z);
ins(x, y, z), ins(y, x, z);
}
DFS(1, 0);
for (int m = 1, x, y, z; m <= M; ++m) {
scanf("%d", &x);
x = dfn[x];
if (!vis[idf[x]]) st.insert(x);
y = idf[(it = st.lower_bound(x)) == st.begin() ? *--st.end() : *--it];
z = idf[(it = st.upper_bound(x)) == st.end() ? *st.begin() : *it];
if (vis[idf[x]]) st.erase(x);
x = idf[x];
LL d = dist(x, y) + dist(x, z) - dist(y, z);
if (!vis[x]) vis[x] = 1, Ans += d;
else vis[x] = 0, Ans -= d;
printf("%lld\n", Ans);
}
return 0;
}