[oiclass2478] Kamp：树形DP+换根+最长链

#include<bits/stdc++.h>
using namespace std;
const int N=500000+5;
struct edge{
	int x,y,z;
};
vector<edge> g[N];
int n,k,has[N],sz[N],son[N];
long long dis1[N],dis2[N],len[N];
void dfs(int u,int fa){
	if(has[u]==1)sz[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].y;
		int w=g[u][i].z;
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
		len[u]+=len[v];
		if(sz[v]==0)continue;
		len[u]+=w;
		if(dis1[v]+w>dis1[u]){
			dis2[u]=dis1[u];
			dis1[u]=dis1[v]+w;
			son[u]=v;
		}else{
			if(dis1[v]+w>dis2[u]){
				dis2[u]=dis1[v]+w;
			}
		}
	}
}
void dp(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].y;
		int w=g[u][i].z;
		if(v==fa)continue;
		
		len[v]=len[u];
		if(sz[v]==0)len[v]+=w;
		if(sz[v]==k)len[v]-=w;
		
		long long out_dis=(son[u]==v?dis2[u]:dis1[u])+w;
		if(out_dis>dis1[v]){
			dis2[v]=dis1[v];
			dis1[v]=out_dis;
			son[v]=u;
		}else{
			if(out_dis>dis2[v]){
				dis2[v]=out_dis;
			}
		}
		dp(v,u);
	}
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1,x,y,z;i<n;i++){
		scanf("%d %d %d",&x,&y,&z);
		g[x].push_back((edge){x,y,z});
		g[y].push_back((edge){y,x,z});
	}
	for(int i=1,x;i<=k;i++){
		scanf("%d",&x);
		has[x]=1;
	}
	dfs(1,-1);
	dp(1,-1);
	for(int i=1;i<=n;i++){
		printf("%lld\n",len[i]*2-dis1[i]);
	}
}