[jzoj3919] [COCI 2014/2015 Round1 KAMP] [자원봉사자] [트리 동태 기획]

제목의 대의.
FJ왕국은 N개의 마을로 이루어져 있고 마을 사이는 나무형 구조를 이루며 마을 사이의 도로는 양방향이다.홍수로 현재 FJ는 K명의 젖소 자원봉사자를 소집해 자원봉사자 1명당 한 마을로 파견돼 구조를 지원하고 있으며, 자원봉사자마다 다른 마을로 파견되고 있다.FJ는 한 마을을 재난 구호의 본거지로 선택하려고 한다. 처음에는 모든 자원봉사자가 이 마을에 있었고 FJ는 스스로 운전기사로 이 K명의 자원봉사자를 자동차로 각자의 목적지까지 데려다 주어야 했다.FJ는 출발하기 전에 모든 젖소 자원봉사자를 그의 차에 싣고 FJ가 스스로 설계한 노선에 따라 최종적으로 모든 젖소를 목적지로 보낼 것이다.FJ는 결국 본영으로 돌아갈 필요가 없다.마을 사이의 도로의 길이가 모두 다르기 때문에 FJ는 어떻게 운행 노선을 설계해야만 자동차의 운행 총 길이를 가장 짧게 할 수 있습니까?FJ는 상황을 더욱 구체적으로 파악하기 위해 N개의 질문을 했다. i번째 질문은 대본영을 i번째 마을에 설치하면 자동차의 주행 총 길이가 가장 짧다는 것이다.여기서 1<=i<=N 입니다.너는 순서대로 이 N개의 문제에 대답해야 한다.
문제풀이의 방향
i번째 질문, 즉 i와 K점의 최소 생성 트리에서 i에서 K점의 가장 먼 거리를 줄인다.K점 최소 생성 트리에 i를 두 배 더해서 생성 트리까지의 거리를 고려하면 i에서 K점 중 가장 먼 거리를 줄일 수 있다.생성 트리는 K개의 점 중 하나를 선택하여 dfs를 한 번 구할 수 있으며 생성 트리 i가 있으면 생성 트리의 거리도 쉽게 구할 수 있다.i에서 K 개의 점 중 가장 먼 곳까지의 거리는 두 부분으로 구성되어 있는데 하나는 서브트리의 부분 mx이다. 이것은 쉽게 구할 수 있고 하나는 나머지 부분 g이다.v는 u의 아버지, g[u]=max(g[u], g[v]+dis(u, v)).mx가 u에 없는 하위 트리, g[u]=max(g[u], mx[v]+dis(u, v)).mx는 u의 서브트리에 있고 g[u]=max(g[u], mx'[v]+dis(u, v)), mx는 차대값이다.이 문제를 해결하다.
code

#include
#include
#include
#include
#define LF double
#define LL long long
#define min(a,b) ((ab)?a:b)
#define fo(i,j,k) for(LL i=j;i<=k;i++)
#define fd(i,j,k) for(LL i=j;i>=k;i--)
using namespace std;
LL const maxn=5*1e5;
LL n,K,gra,sum,to[maxn*2+10],len[maxn*2+10],next[maxn*2+10],
begin[maxn+10],cnt[maxn+10],f[maxn+10],g[maxn+10],dep[maxn+10],
mx[maxn+10],mx2[maxn+10],mxbel[maxn+10];
void insert(LL u,LL v,LL w){
    to[++gra]=v;
    len[gra]=w;
    next[gra]=begin[u];
    begin[u]=gra;
}
void dfs(LL now,LL pre){
    for(LL i=begin[now];i;i=next[i])if(to[i]!=pre){
        dep[to[i]]=dep[now]+len[i];
        dfs(to[i],now);
        cnt[now]+=cnt[to[i]];
        if(cnt[to[i]]){
            if(mx[to[i]]+len[i]>mx[now]){
                mx2[now]=mx[now];
                mx[now]=mx[to[i]]+len[i];
                mxbel[now]=to[i];
            }else mx2[now]=max(mx2[now],mx[to[i]]+len[i]);
            sum+=len[i]*2;
        }
    }
}
void dfss(LL now,LL pre,LL tmp){
    f[now]=dep[now]-dep[tmp];
    for(LL i=begin[now];i;i=next[i])if(to[i]!=pre){
        //g[to[i]]=max(g[now]+len[i],(mxbel[now]!=to[i])?(mx[now]+len[i]):(mx2[now]+len[i]));
        if(mxbel[now]!=to[i])g[to[i]]=max(g[now],mx[now])+len[i];
        else g[to[i]]=max(g[now],mx2[now])+len[i];
        dfss(to[i],now,(cnt[to[i]])?to[i]:tmp);
    }
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%lld%lld",&n,&K);LL u,v,w,st;
    fo(i,2,n){
        scanf("%lld%lld%lld",&u,&v,&w);
        insert(u,v,w);insert(v,u,w);
    }
    fo(i,1,K)scanf("%lld",&u),cnt[u]++,st=u;
    dep[st]=1;dfs(st,0);
    dfss(st,0,st);
    fo(i,1,n)printf("%lld
",sum+f[i]*2-max(g[i],mx[i]));
    return 0;
}