题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3991
可以发现答案是所有相邻藏宝点的lca和（第一个和最后一个也算相邻）
然后开个set维护一下插入和删除（插入inf和-inf就可以快速定位辣）。
#include<cstring> #include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<set> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 105000 #define inf int(1e9) #define mm 1000000007 typedef long long ll; using namespace std; struct data{int obj,pre;ll c; }e[maxn*2]; int bin[22],n,m,tot,idx; int b[maxn],head[maxn],fa[maxn][22],dep[maxn],dfn[maxn],num[maxn]; ll d[maxn]; set<int> q; ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int y,ll z){ e[++tot].obj=y; e[tot].pre=head[x]; e[tot].c=z; head[x]=tot; } void dfs(int u){ rep(i,1,20) if (dep[u]>=bin[i]) { fa[u][i]=fa[fa[u][i-1]][i-1]; } dfn[u]=++idx; num[dfn[u]]=u; for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (v!=fa[u][0]){ d[v]=d[u]+e[j].c; dep[v]=dep[u]+1; fa[v][0]=u; dfs(v); } } } int lca(int x,int y){ if (dep[x]<dep[y]) swap(x,y); int t=dep[x]-dep[y]; rep(i,0,20) if (t&bin[i]) x=fa[x][i]; down(i,20,0) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; if (x==y) return x; return fa[x][0]; } ll dis(int x,int y){ int t=lca(x,y); return d[x]+d[y]-2*d[t]; } int main(){ // freopen("in.txt","r",stdin); bin[0]=1; rep(i,1,20) bin[i]=bin[i-1]*2; n=read(); m=read(); rep(i,1,n-1){ int x=read(),y=read();ll z=read(); insert(x,y,z); insert(y,x,z); } dep[1]=1; dfs(1); q.insert(inf); q.insert(-inf); ll ans=0,tmp=0; int now,f; rep(i,1,m){ int x=read(); now=dfn[x]; f=1; if (b[x]){ f=-1; q.erase(now); } else q.insert(now); b[x]^=1; int l=*--q.lower_bound(now),r=*q.upper_bound(now); if (l!=-inf) ans+=f*dis(x,num[l]); if (r!=inf) ans+=f*dis(x,num[r]); if (l!=-inf&&r!=inf) ans-=f*dis(num[l],num[r]); if (q.size()!=2) tmp=dis(num[*q.upper_bound(-inf)],num[*--q.lower_bound(inf)]); printf("%lld ",ans+tmp); } return 0; }