题解: 我只是一个不想写虚树的孩子呀 QWQ
首先我把$ K $个点的$ LCA $求出来作为根 所有从$ K $到根所经过的节点都被称为关键节点 对于每个点找到离他最近的关键节点
然后对于答案 对于$ y $必然是 $ ans=sum+dis[y]-dis[x]-Len $.$ sum $是所有关键点的路径的和的2倍.$ x $是离$ y $最近的关键点.$ Len $是$ K $个节点中离$ y $最远的点的距离
然后做树dp就行了
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=5e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int p[MAXN],pos[MAXN];
bool vis[MAXN];
ll dep[MAXN],ans;
int num[MAXN],rt,base;
void ___dfs(int x,int pre){
link(x){
if(j->t==pre)continue;
___dfs(j->t,x);
num[x]+=num[j->t];
}
if(!rt&&num[x]==base)rt=x;
}
void dfs(int x,int pre){
link(x){
if(j->t==pre)continue;
dep[j->t]=dep[x]+j->v;
dfs(j->t,x);
if(vis[j->t])vis[x]=1,ans+=j->v;
}
}
ll dp[MAXN];
void _dfs(int x,int pre,int k){
int y=k;
if(vis[x])y=x,pos[x]=x;
else pos[x]=y;
link(x){
if(j->t==pre)continue;
_dfs(j->t,x,y);
if(vis[j->t])dp[x]=max(dp[x],dp[j->t]+j->v);
}
}
ll up[MAXN];
ll st[MAXN],St[MAXN],b[MAXN];
int tot;
ll maxx[MAXN];
void __dfs(int x,int pre){
tot=0;
link(x){
if(j->t==pre)continue;
if(vis[j->t])b[++tot]=dp[j->t]+j->v;
else b[++tot]=0;
}
st[0]=St[tot+1]=0;
inc(i,1,tot)st[i]=max(st[i-1],b[i]);
dec(i,tot,1)St[i]=max(St[i+1],b[i]);
int cnt=0;
link(x){
if(j->t==pre)continue;
cnt++;
up[j->t]=max(up[x],max(st[cnt-1],St[cnt+1]))+j->v;
maxx[j->t]=max(up[j->t],dp[j->t]);
}
link(x){
if(j->t==pre)continue;
__dfs(j->t,x);
}
}
int main(){
int n=read();int k=read();
int x,y,z;rt=0;base=k;
inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
inc(i,1,k)p[i]=read(),vis[p[i]]=1,num[p[i]]=1;
___dfs(1,0);
ans=0;
dfs(rt,0);_dfs(rt,0,0);
__dfs(rt,0);maxx[rt]=dp[rt];
ans<<=1;
// cout<<rt<<" "<<ans<<endl;
// inc(i,1,n)cout<<dp[i]<<" ";
// cout<<endl;
inc(i,1,n){
ll t=ans+dep[i]-dep[pos[i]];
t-=maxx[pos[i]];
printf("%lld
",t);
}
return 0;
}
3743: [Coci2015]Kamp
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 684 Solved: 331
[Submit][Status][Discuss]
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个点举行聚会，司机需要的最少时间。
Sample Input
7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7
Sample Output
11
15
10
13
16
15
10
15
10
13
16
15
10
HINT
【数据规模】
K <= N <= 500000
1 <= x,y <= N, 1 <= z <= 1000000