P1017 · OFFICIAL SOLUTION

P1017 黑流树海官方题解

Gioush OJ · P1017 黑流树海

黑流树海

【题意简述】

给定一棵带权树与 $k$ 个关键点。对于每个起点 $u$ ，求从 $u$ 出发访问所有关键点且不要求回到起点的最小路程。

【部分分】

若固定起点，必须经过连接所有关键点与起点的最小连通子树。若所有边都需要走完并返回，代价是子树边权和的两倍；由于最后不需要返回，可以省去从起点到某个关键点的最长距离。

【正解】

设 $F(u)$ 表示从 $u$ 出发时需要覆盖的最小子树边权和的两倍，设 $D(u)$ 表示 $u$ 到关键点的最远距离，则答案为 $F(u)-D(u)$ 。第一次 DFS 以 $1$ 为根，求每个子树内关键点数量、子树贡献与向下最远关键点距离。第二次 DFS 换根，维护父侧是否含有关键点，以及来自父侧的最远距离。这样每个点都能得到完整的 $F(u)$ 与 $D(u)$ 。

【复杂度】

两次 DFS 均只经过每条边常数次，时间复杂度为 $\mathcal{O}(n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。距离与答案需要使用 long long。

【参考代码】

1#include <cstdio>2#include <cstring>3#include <algorithm>4#define MAXN 5001005using namespace std;6int Head[MAXN],Total=0,n,m,k;7long long Dp[MAXN],Size[MAXN],Dis[MAXN][2],Ans[MAXN],F[MAXN];8bool Key[MAXN];9struct edge{10    int St,Ed,Next;11    int Value;12}Edge[MAXN<<1];13void Edge_Add(int St,int Ed,int Value){14    Edge[++Total]={St,Ed,Head[St],Value};15    Head[St]=Total;16}17void DFS(int Now,int From){18    if(Key[Now]) Size[Now]=1;19    else Size[Now]=0;20    for(int i=Head[Now];i;i=Edge[i].Next){21        int To=Edge[i].Ed;22        if(To==From) continue;23        DFS(To,Now);24        Size[Now]+=Size[To];25        if(Size[To]){26            Dp[Now]+=2*Edge[i].Value+Dp[To];27            if(Dis[To][0]+Edge[i].Value>Dis[Now][0]){28                Dis[Now][1]=Dis[Now][0];29                Dis[Now][0]=Dis[To][0]+Edge[i].Value;30            }31            else if(Dis[To][0]+Edge[i].Value>Dis[Now][1]){32                Dis[Now][1]=Dis[To][0]+Edge[i].Value;33            }34        }35    }36}37void Dynamic(int Now,int From,int LastLen){38    if(Now==1) Ans[Now]=Dp[Now]-Dis[Now][0],F[1]=Dp[1];39    else{40        if(Size[Now]==0) F[Now]=F[From]+2*LastLen;41        else if(k-Size[Now]==0) F[Now]=Dp[Now];42        else F[Now]=F[From];43        long long NowD;44        if(Size[Now]&&Dis[From][0]==LastLen+Dis[Now][0]){45            NowD=Dis[From][1]+LastLen;46            if(Dis[From][1]==0&&!Key[From]) NowD=-1;47        }48        else NowD=Dis[From][0]+LastLen;49        if(NowD>Dis[Now][0]){50            Dis[Now][1]=Dis[Now][0];51            Dis[Now][0]=NowD;52        }53        else if(NowD>Dis[Now][1]){54            Dis[Now][1]=NowD;55        }56        Ans[Now]=F[Now]-Dis[Now][0];57    }58    for(int i=Head[Now];i;i=Edge[i].Next){59        int To=Edge[i].Ed;60        if(To==From) continue;61        Dynamic(To,Now,Edge[i].Value);62    }63    return ;64}65int main(){66    freopen("tide.in","r",stdin);67    freopen("tide.out","w",stdout);68    int In1,In2,In3;69    scanf("%d%d",&n,&k);70    for(int i=1;i<=n-1;i++){71        scanf("%d%d%d",&In1,&In2,&In3);72        Edge_Add(In1,In2,In3);73        Edge_Add(In2,In1,In3);74    }75    for(int i=1;i<=k;i++){76        scanf("%d",&In1);77        Key[In1]=true;78    }79    DFS(1,1);80    Dynamic(1,1,0);81    for(int i=1;i<=n;i++){ printf("%lld\n",Ans[i]);}82}