在考试代码的基础上稍微改改就a了……当时为什么不稍微多想想……
插入/删除一个新节点时就把其dfn插入set/从set中删除。
当前的答案就是dfn上相邻的两两节点的距离和，再加上首尾节点的距离。
比较显然？不会证明……
貌似叫“虚树”？
#include<cstdio>
#include<set>
using namespace std;
#define N 100001
typedef long long ll;
set<int>S;
typedef set<int>::iterator ER;
int n,m;
int v[N<<1],first[N],next[N<<1],w[N<<1],en;
void AddEdge(int U,int V,int W)
{
v[++en]=V;
w[en]=W;
next[en]=first[U];
first[U]=en;
}
int top[N],dep[N],fa[N],siz[N],son[N],dfn[N],Map[N];
ll sumv[N],ans;
bool a[N];
void dfs(int U)
{
siz[U]=1;
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U])
{
fa[v[i]]=U;
dep[v[i]]=dep[U]+1;
sumv[v[i]]=sumv[U]+(ll)w[i];
dfs(v[i]);
siz[U]+=siz[v[i]];
if(siz[v[i]]>siz[son[U]])
son[U]=v[i];
}
}
void df2(int U)
{
dfn[U]=++en;
Map[en]=U;
if(son[U])
{
top[son[U]]=top[U];
df2(son[U]);
}
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U]&&v[i]!=son[U])
{
top[v[i]]=v[i];
df2(v[i]);
}
}
int lca(int U,int V)
{
while(top[U]!=top[V])
{
if(dep[top[U]]<dep[top[V]])
swap(U,V);
U=fa[top[U]];
}
if(dep[U]>dep[V])
swap(U,V);
return U;
}
ll Query(int U,int V)
{
return sumv[U]+sumv[V]-(sumv[lca(U,V)]<<1);
}
int main()
{
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
en=0;
top[1]=1;
dfs(1);
df2(1);
for(;m;--m)
{
scanf("%d",&x);
a[x]^=1;
if(a[x])
{
S.insert(dfn[x]);
ER it=S.end(); --it;
ER jt=S.begin();
if(S.size()==0||S.size()==1) ans=0;
if(S.size()==2)
ans=(Query(Map[*jt],Map[*it])<<1);
else if(S.size()>2&&(*jt)==dfn[x])
{
ans+=Query(Map[*jt],Map[*it]);
ER kt=jt; ++kt;
ans+=Query(Map[*jt],Map[*kt]);
ans-=Query(Map[*kt],Map[*it]);
}
else if(S.size()>2&&(*it)==dfn[x])
{
ans+=Query(Map[*jt],Map[*it]);
ER kt=it; --kt;
ans+=Query(Map[*it],Map[*kt]);
ans-=Query(Map[*kt],Map[*jt]);
}
else if(S.size()>2)
{
ER kt=S.find(dfn[x]);
ER lt=kt; --lt;
ER mt=kt; ++mt;
ans+=Query(Map[*lt],Map[*kt]);
ans+=Query(Map[*kt],Map[*mt]);
ans-=Query(Map[*lt],Map[*mt]);
}
}
else
{
ER it=S.end(); --it;
ER jt=S.begin();
if(S.size()==0||S.size()==1) ans=0;
if(S.size()==2)
ans=(Query(Map[*jt],Map[*it])<<1);
else if(S.size()>2&&(*jt)==dfn[x])
{
ans-=Query(Map[*jt],Map[*it]);
ER kt=jt; ++kt;
ans-=Query(Map[*jt],Map[*kt]);
ans+=Query(Map[*kt],Map[*it]);
}
else if(S.size()>2&&(*it)==dfn[x])
{
ans-=Query(Map[*jt],Map[*it]);
ER kt=it; --kt;
ans-=Query(Map[*it],Map[*kt]);
ans+=Query(Map[*kt],Map[*jt]);
}
else if(S.size()>2)
{
ER kt=S.find(dfn[x]);
ER lt=kt; --lt;
ER mt=kt; ++mt;
ans-=Query(Map[*lt],Map[*kt]);
ans-=Query(Map[*kt],Map[*mt]);
ans+=Query(Map[*lt],Map[*mt]);
}
S.erase(dfn[x]);
}
printf("%lld
",ans);
}
return 0;
}