前言

美妙树剖，比较套路了吧，反正一眼秒了。

原本不想补题解的，但是做到这题还是我的御用纯情娇羞可爱内向小男娘 Loser_Syx 把这题推给我了捏。

博客内食用更佳。

思路分析

题目这么大个式子摆在眼前肯定先考虑暴力化简下啊。

题目给定的一个函数外面再套求和肯定是不太好做的，所以考虑先拆里面。

里面的直接使用树上距离公式就行了（注意这里的深度是指到根节点的距离）。

$$dis(x,y)=dep_x+dep_y-2\times dep_{LCA(x,y)}$$

用这个式子就可以把之前那个又臭又长的式子破开成为：

$$\sum\limits_{i=1}^k\sum\limits_{j=1}^k dep_{a_i}+dep_{a_j}-2\times dep_{LCA(a_i,a_j)}$$

然后把这里面好算的东西拿出来破开：

$$2\times(k-1)\times \sum\limits_{i=1}^kdep_{a_i}-4\times\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kdep_{LCA(a_i,a_j)}$$

（虽然我感觉很惊讶，但是另一篇题解后面的这个系数好像写错了，应该是 $4$，原因是把从 $1$ 开始变为从 $i+1$ 开始应该再乘上一个 $2$ 的系数。）

然后把前面一坨和后面那一坨分开，也就是令

$ans1=\sum\limits_{i=1}^kdep_{a_i},ans2=\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kdep_{LCA(a_i,a_j)}$。

然后前面那玩意很好维护了，出新点的时候直接加上这个点即可。

重点则在后面这一块怎么求。

首先思考下这一坨他在树上的意义是什么？

是根到他们 LCA 的距离吗？（那不是说了和说了一样。）

所以考虑为什么我们可以把 $dis(x,y)$ 拆开的原因。

那他的意义即为：$1\rightarrow a_i,1\rightarrow a_j$ 路径相交的长度。

路径相交？那我们便可以在把一个村庄 $i$ 变为新的城堡后把 $1\rightarrow i$ 上的路径的边权全部倍数 $+1$。

查询的时候只要直接询问 $1\rightarrow i$ 上的路径长度求出来加入 $ans2$ 中即可。

具体细节见又臭又长的代码了。

代码

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=200010,INF=0x3f3f3f3f3f3f3f3f;
struct edge
{int v,nxt,w;}e[N<<1];
int n,k,tot,cnt,ans1,ans2;
int head[N],top[N],id[N],dfn[N],a[N];
int fa[N],dep[N],son[N],si[N];
int lz[N<<2],s[N<<2],re[N<<2];
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void){
    int x(0),a(1);char fc(getchar());
    while(!isdigit(fc)){if(fc=='-') a=-1;fc=getchar();}
    while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
    return x*a;
}
inline void print(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
void add(int u,int v,int w){e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot,e[tot].w=w;}
void dfs1(int u,int ff)
{
	fa[u]=ff,si[u]=1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==ff) continue;
		a[v]=e[i].w;dep[v]=dep[u]+a[v];
		dfs1(v,u);si[u]+=si[v];
		if(si[v]>si[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int topf)
{
	top[u]=topf,dfn[u]=++cnt,id[cnt]=a[u];
	if(son[u]) dfs2(son[u],topf);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==son[u]||v==fa[u]) continue;
		dfs2(v,v);
	}
}
void pushdown(int p){lz[ls]+=lz[p],lz[rs]+=lz[p],re[ls]+=s[ls]*lz[p],re[rs]+=s[rs]*lz[p],lz[p]=0;}
void build(int p,int l,int r)
{
	if(l==r) return void(s[p]=id[l]);
	build(ls,l,mid),build(rs,mid+1,r);s[p]=s[ls]+s[rs];
}
void modify(int p,int l,int r,int st,int ed)
{
	if(l>ed||r<st) return;
	if(l>=st&&r<=ed) return void(lz[p]++),void(re[p]+=s[p]);pushdown(p);
	modify(ls,l,mid,st,ed);modify(rs,mid+1,r,st,ed);re[p]=re[ls]+re[rs];
}
int query(int p,int l,int r,int st,int ed)
{
	if(l>ed||r<st) return 0;if(l>=st&&r<=ed) return re[p];
	pushdown(p);return query(ls,l,mid,st,ed)+query(rs,mid+1,r,st,ed);
}
signed main()
{
    n=read(),k=read();
    for(int i=1,u,v,w;i<n;i++) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
    dfs1(1,0),dfs2(1,1);build(1,1,n);ans1+=dep[1];
	ans2+=query(1,1,n,dfn[1],dfn[1]);modify(1,1,n,dfn[1],dfn[1]);
    for(int i=1,x;i<=k;i++)
    {
    	x=read();ans1+=dep[x];
		while(x)
		{
			ans2+=query(1,1,n,dfn[top[x]],dfn[x]);
			modify(1,1,n,dfn[top[x]],dfn[x]);
			x=fa[top[x]];
		}print(2*ans1*i-ans2*4);puts("");
	}
    return 0;
}