洛谷 P8509 题解（待完善）

题面。

要求所有点到关键点的距离和最小。

首先要确定这个点去哪个关键点最短。

树上两点间路径与距离是唯一的，所以

我们从两个关键点分别跑dfs。

第一遍求出每个点到s的最短距离。

然后再从t点出发，如果这个点到t点的距离更短，那么这个点就应该去t点。

定向的工作也可以在dfs的时候做。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int h=600010;
int head[h],last[h],to[h],tot=1;
ll len[h];
void add_edge(int x,int y,ll w){
    tot++;
    last[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    len[tot]=w;
}
void add(int x,int y,ll w){
    add_edge(x,y,w);
    add_edge(y,x,w);
}
int n,s,t;
ll dis[h];
bool ch[h];
void clear(int now){
    for(int i=head[now];i;i=last[i])
        ch[i]=0,ch[i^1]=0;
}
void dfs(int now,int fa){
    for(int i=head[now];i;i=last[i]){
        int nex=to[i];
        if(nex^fa)
            if(dis[nex]>dis[now]+len[i])
                clear(nex),dis[nex]=dis[now]+len[i],ch[i]=0,ch[i^1]=1,dfs(nex,now);
    }
}
ll d;
int main(){
    scanf("%d%d%d",&n,&s,&t);
    for(int i=1,u,v;i<n;i++)
        scanf("%d%d%lld",&u,&v,&d),add(u,v,d);
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,dis[t]=0;
    dfs(s,0),dfs(t,0);
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=dis[i];
    printf("%lld\n",ans);
    for(int i=1;i<n;i++)
        if(ch[i*2])
            putchar('1');
        else
            if(ch[i*2+1])
                putchar('2');
            else
                putchar('0');
    return 0;
}