我努力奔跑,只为追上曾经被寄予厚望的自己

bzoj3743 [COCI2015]Kamp

2018-11-07 15:47:49


题意:一棵有边权树,要从一个点出发,遍历 $m$ 个关键点。除了最后一个遍历的,都需要回到起点。对于 $i∈[1,n]$ ,求出从该点出发完成任务的最短距离。


考虑以一个关键点为根,把关键点建立一棵树

这样 $i$ 号点的答案就是这棵树的边权和 $\times 2+i$ 号点到这棵树的最短距离(记为 $j$ 点) $-j$ 到树上一点的最远距离

因为树上的边至少走两次,从 $i$ 到树上肯定要走最短距离,最后一个遍历的点不需要回到起点,所以一定是把距离最远的点作为终点

所以可以用 $4$ 个 $dfs$

  • 求出每个点是否在新建的树上,并计算树的边权和 $(on,sum)$

  • 找到每个点到树的最短距离以及最近点 $(dis,nrp)$

  • 找到树上每个点对应的最长链和次长链 $(f,g)$

  • 求出树上每个点到其他点的最远距离 $(d)$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct node
{
    int to,nxt,dis;
}edge[N<<1];
int n,m,num,head[N],on[N],rt,nrp[N],son[N];
ll sum,f[N],g[N],dis[N],d[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to,int dis)
{
    edge[++num]=(node){to,head[from],dis};
    head[from]=num;
}
bool dfs1(int k,int fa)
{
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa) continue;
        if (dfs1(v,k)) on[k]=1,sum+=edge[i].dis;
    }
    return on[k];
}
void dfs2(int k,int fa)
{
    if (on[k]) nrp[k]=k;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa) continue;
        if (!on[v]) nrp[v]=nrp[k],dis[v]=dis[k]+edge[i].dis;
        dfs2(v,k);
    }
}
void dfs3(int k,int fa)
{
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa||!on[v]) continue; dfs3(v,k);
        ll now=f[v]+edge[i].dis;
        if (now>f[k]) g[k]=f[k],f[k]=now,son[k]=v;
        else g[k]=max(g[k],now);
    }
}
void dfs4(int k,int fa,ll dt)
{
    d[k]=max(f[k],dt);
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==fa||!on[v]) continue;
        dfs4(v,k,max(dt,(v==son[k]?g[k]:f[k]))+edge[i].dis);
    }
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read(),z=read();
        add_edge(x,y,z); add_edge(y,x,z);
    }
    for (reg int i=1;i<=m;i++) on[rt=read()]=1;
    dfs1(rt,0); dfs2(rt,0); dfs3(rt,0); dfs4(rt,0,0);
    for (reg int i=1;i<=n;i++) printf("%lld\n",sum*2+dis[i]-d[nrp[i]]);
    return 0;
}