Description
一颗树n个点，n-1条边，经过每条边都要花费一定的时间，任意两个点都是联通的。
有K个人（分布在K个不同的点）要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发，把这K个人分别送回去。
请你回答，对于i=1~n，如果在第i个点举行聚会，司机最少需要多少时间把K个人都送回家。
Input
第一行两个数，n，K。
接下来n-1行，每行三个数，x，y，z表示x到y之间有一条需要花费z时间的边。
接下来K行，每行一个数，表示K个人的分布。
Output
输出n个数，第i行的数表示：如果在第i个点举行聚会，司机需要的最少时间。
树形dp
定义人所在位置为标记点
求出结点i到每个标记点的路径经过的边的总长b[i]
求出结点i到标记点的最远距离c[i]，过程中还要记录次远距离c2[i]
每个结点的答案即为b[i]*2-c[i]
转化为有根树，第一次dfs用子节点信息更新父节点信息
第二次dfs用父节点信息更新子节点信息
#include<cstdio>
#include<vector>
#define N 500005
typedef long long lint;
struct edge{
int to,w;
edge(int _,int __){to=_,w=__;}
};
std::vector<edge>v[N];
bool d[N];
lint a[N],b[N],c[N],c2[N];
int cp[N];
int n,k,p1,p2,p3;
,){
;
,u;~i;i--){
if((u=v[w][i].to)==pa)continue;
int l=v[w][i].w;
dfs1(u,w);
a[w]+=a[u];
b[w]+=b[u];
if(a[u])b[w]+=l;
else continue;
if(c[u]+l>=c[w])c2[w]=c[w],c[w]=c[u]+l,cp[w]=u;
else if(c[u]+l>=c2[w])c2[w]=c[u]+l;
}
}
,){
,u;~i;i--){
if((u=v[w][i].to)==pa)continue;
int l=v[w][i].w;
b[u]=b[w];
)b[u]-=l;
if(a[u]<k)b[u]+=l;
lint m=(u==cp[w]?c2[w]:c[w])+l;
;
else if(m>=c2[u])c2[u]=m;
dfs2(u,w);
}
}
int main(){
scanf("%d%d",&n,&k);
;i<n;i++){
scanf("%d%d%d",&p1,&p2,&p3);
v[p1].push_back(edge(p2,p3));
v[p2].push_back(edge(p1,p3));
}
;i<k;i++)scanf(;
dfs1(),dfs2();
;i<=n;i++)printf(-c[i]);
;
}