Description：

给一棵树，边有边权，每次添加一个点或者删除一个点，询问走过所有点回到出发点的最短长度。

$1\leqslant n\leqslant 10^5$

Solution：

先求出这棵树的 $dfs$ 序，然后添加一个点就在 $set$ 里查一下前驱后继，减去他们之间的距离，加上这个点分别到他们的距离，如果不存在前驱那么就是整个 $set$ 的最后一个，如果不存在后继那么就是第一个，因为可以看成是循环的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

typedef long long ll;

struct edge

{

	int to,nxt;

	ll w;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll v)

{

	e[++edgenum] = (edge){b,lin[a],v};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],v};lin[b] = edgenum;

	return;

}

int fa[MAXN],siz[MAXN],dep[MAXN],son[MAXN],top[MAXN];

ll dis[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dis[e[i].to] = dis[k] + e[i].w;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

int dfn[MAXN],th[MAXN],tot = 0;

void dfs2(int k,int tp)

{

	top[k] = tp;

	dfn[k] = ++tot;th[tot] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

ll dist(int a,int b)

{

	return dis[a] + dis[b] - 2 * dis[LCA(a,b)];

}

int type[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;ll v;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%lld",&a,&b,&v);

		add(a,b,v);

	}

	dfs1(1,1);dfs2(1,1);

	set<int> s;

	long long ans = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&a);

		if(type[a] == 0)

		{

			set<int>::iterator it = s.lower_bound(dfn[a]);

			if(!s.empty())

			{

				int pre,nxt;

				if(it != s.begin()){set<int>::iterator p = it;--p;pre = *p;}

				else{set<int>::iterator p = s.end();--p;pre = *p;}

				if(it != s.end())nxt = *it;

				else nxt = *s.begin();

				pre = th[pre];nxt = th[nxt];

				ans = ans - dist(pre,nxt) + dist(pre,a) + dist(nxt,a);

			}

			s.insert(dfn[a]);

		}

		else

		{

			s.erase(dfn[a]);

			set<int>::iterator it = s.lower_bound(dfn[a]);

			if(!s.empty())

			{

				int pre,nxt;

				if(it != s.begin()){set<int>::iterator p = it;--p;pre = *p;}

				else{set<int>::iterator p = s.end();--p;pre = *p;}

				if(it != s.end())nxt = *it;

				else nxt = *s.begin();

				pre = th[pre];nxt = th[nxt];

				ans = ans + dist(pre,nxt) - dist(pre,a) - dist(nxt,a);

			}

		}

		printf("%lld\n",ans);

		type[a] ^= 1;

	}

	return 0;

}