【题目来源】
【题目描述】
一棵树 n 个点，n-1 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。
有 K 个人（分布在 K 个不同的点）要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发，先让所有人都上车，再把这 K 个人分别送回去。请你回答，对于 i=1~n，如果在第 i 个点举行聚会，司机最少需要多少时间把 K 个人都送回家。
【输入格式】
第一行两个整数 n，K。
接下来 n-1 行，每行三个数 x，y，z 表示 x 到 y 之间有一条需要花费z时间的边。
接下来 K 行，每行一个数，表示 K 个人的分布。
【输出格式】
输出 n 个数。
第 i 行的数表示：如果在第 i 个点举行聚会，司机需要的最少时间。
【输入样例一】
7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7
【输出样例一】
11
15
10
13
16
15
10
【输入样例二】
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5
【输出样例二】
5
3
7
2
2
【数据范围】
对于 50% 的数据，保证n≤2×10^3。
对于 100% 的数据，1≤K≤n<5×10^5，1≤x, y≤n，1≤z≤10^8。
【算法分析】
● 快读：
int read() { //fast readint x=0,f=1;char c=getchar();while(c<'0' || c>'9') { //!isdigit(c)if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') { //isdigit(c)x=x*10+c-'0';c=getchar();}return x*f;
}
本题可以不用“快读”，也可以使用 scanf 完成输入。
● 链式前向星：
void add(int a,int b,int w) {val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}大佬 yxc 指出“链式前向星”就是“多单链表”，每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中：
e[idx]：存储序号为 idx 的边的终点值
ne[idx]：存储序号为 idx 的边指向的边的序号（模拟链表指针）
h[a]：存储头结点 a 指向的边的序号
val[idx]：存储序号为 idx 的边的权值（可选）
【算法代码】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=5e5+5;int val[N<<1],e[N<<1],ne[N<<1],h[N],idx=1;
void add(int a,int b,int w) {val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool st[N]; //st[u] indicates whether u is a key point
int siz[N]; //siz[u] represents critical points'num in the subtree of node u
LL f[N]; //f[u] stores total path length for all key points from u
LL g[N]; //g[u] stores double sum of edge weights within the subtree of u
LL up[N]; //up[u] stores the maximum distance from u above it
LL down[N]; //down[u] stores the maximum distance from u under it
LL secd[N]; //secd[u] stores the secondary distance from u under it
int n,k;void dfs(int u,int fa) {siz[u]=st[u];for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];LL w=val[i];if(j==fa) continue;dfs(j,u);siz[u]+=siz[j];if(siz[j]) {g[u]+=g[j]+2*w;if(down[j]+w>down[u]) {secd[u]=down[u];down[u]=down[j]+w;} else if(down[j]+w>secd[u]) {secd[u]=down[j]+w;}}}
}void dfs(int u,int fa,LL w) {if(siz[u]==k) {f[u]=g[u];up[u]=0;} else if(siz[u]==0) {f[u]=f[fa]+2*w;up[u]=max(up[fa],down[fa])+w;} else {f[u]=f[fa];if(down[fa]-down[u]==w) {up[u]=max(up[fa],secd[fa])+w;} else up[u]=max(up[fa],down[fa])+w;}for(int i=h[u]; i!=-1; i=ne[i]) {int v=e[i];LL w=val[i];if(v==fa) continue;dfs(v,u,w);}
}int main() {memset(h,-1,sizeof h);cin>>n>>k;for(int i=1; i<n; i++) {int u,v;LL w;scanf("%d%d%lld",&u,&v,&w);add(u,v,w);add(v,u,w);}for(int i=1; i<=k; i++) {int x;scanf("%d",&x);st[x]=true;}dfs(1,0);dfs(1,0,0);for(int i=1; i<=n; i++) {printf("%lld\n",f[i]-max(up[i],down[i]));}return 0;
}/*
in:
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4
5out:
5
3
7
2
2
*/
【参考文献】