参考这里
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
int n, m, ise[100005], fa[100005][19], dep[100005], uu, vv, ww, hea[100005], cnt;
int faq, nfd[100005];
ll dis[100005], ans;
struct Edge{
int too, nxt, val;
}edge[200005];
struct Node{
int idx, dfn;
bool operator<(const Node &x)const{
return dfn<x.dfn;
}
};
set<Node> qwq;
void add_edge(int fro, int too, int val){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
edge[cnt].val = val;
hea[fro] = cnt;
}
void dfs(int x, int f, ll d){
nfd[x] = ++faq;
dis[x] = d;
fa[x][0] = f;
dep[x] = dep[f] + 1;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f) dfs(t, x, d+edge[i].val);
}
}
int queryPre(int x){
set<Node>::iterator i=qwq.lower_bound((Node){x, nfd[x]});
if(i==qwq.begin()) i = qwq.end();
return (*(--i)).idx;
}
int queryNxt(int x){
set<Node>::iterator i=qwq.lower_bound((Node){x, nfd[x]});
if((++i)==qwq.end()) i = qwq.begin();
return (*i).idx;
}
int lca(int x, int y){
if(dep[x]<dep[y]) swap(x, y);
for(int i=16; i>=0; i--)
if(dep[fa[x][i]]>=dep[y])
x = fa[x][i];
if(x==y) return x;
for(int i=16; i>=0; i--)
if(fa[x][i]!=fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
ll qdis(int x, int y){
return dis[x]+dis[y]-2*dis[lca(x, y)];
}
ll query(int x){
int pre, nxt, fla;
if(!ise[x]){
fla = 1;
qwq.insert((Node){x, nfd[x]});
pre = queryPre(x);
nxt = queryNxt(x);
}
else{
fla = -1;
pre = queryPre(x);
nxt = queryNxt(x);
qwq.erase((Node){x, nfd[x]});
}
ise[x] ^= 1;
if(qwq.size()<=1) ans = 0;
else ans += fla * (qdis(pre, x)+qdis(x, nxt)-qdis(pre, nxt));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1; i<n; i++){
scanf("%d %d %d", &uu, &vv, &ww);
add_edge(uu, vv, ww);
add_edge(vv, uu, ww);
}
dfs(1, 0, 0);
for(int i=1; i<=16; i++)
for(int j=1; j<=n; j++)
fa[j][i] = fa[fa[j][i-1]][i-1];
while(m--){
scanf("%d", &uu);
printf("%lld
", query(uu));
}
return 0;
}