题解 P5898 【[COCI 2015]Kamp】

· · 题解

感觉楼上两篇题解写的都不是很清楚，窝来详细地解释一下

首先，第一眼，这是一道换根dp

接下来我们就要看两次dfs要处理什么

The first dfs

按照换根dp的老套路，我们要处理子树里的信息

我们令 g_u 为以 u 为根的子树中从 u 开始把所有家在这个子树内的人送回家并回到 u 节点的最短路程

再令 sz_u 为家在以 u 为根的子树中的人数

显然，我们珂以得到 g_u=\sum g_v+2\times w_{u\rightarrow v} 其中 v 为 u 的子节点，且 sz_v\neq 0

其中 w 为边权

刚做这道题的我天真地以为这就是第一次 dfs 需要处理的东西，当我写完之后测样例时，发现挂掉了，所以，我们还需要处理一些东西

我们手算了一遍样例，发现我们的车可以送完人了之后不返回开始点；也就是说再我们这么算回到起始点的树值之后还要减去一个最长链的长度

这里的最长链就表示离一个点最远的人的家

那么我们令 len_u 为从 u 开始的最长链，id_u 为从 u 开始的最长链所经过的第一个节点（也就是 u 的一个子节点或者 u 的父亲节点），slen_u 为从 u 开始的次长链

次长链是干啥的待会再说

当然了，第一次dfs我们还是只处理子树内的最长链，次长链

先放第一次dfs的代码：

void dfs(int u,int fa)
{
    if(pos[u])sz[u]=1;
    for(int i=Head[u];i;i=Edge[i].next)
    {
        int v=Edge[i].to,w=Edge[i].val;
        if(v==fa)continue;
        dfs(v,u);
        if(sz[v])//当v的子树中有人才更新
        {
            g[u]+=g[v]+2*w;
            int now=len[v]+w;
            if(now>=len[u])slen[u]=len[u],len[u]=now,id[u]=v;//最长链
            else if(now>slen[u])slen[u]=now;//次长链
        }
        sz[u]+=sz[v];
    }
}

the second dfs

第二次dfs我们就要处理全局的事情了qwq

令 f_u 为对于整棵树从 u 开始送人最后回到 u 的最短距离

接下来我们就要开始分类了qwq

1、当以 u 为根的子树中没有人的家，即 sz_u=0 时，我们发现 f_v=f_u+2\times w_{u\rightarrow v} ，很好理解，不多说了（画画图就好了
2、当除了以 u 为根的子树其他地方没有人的家，即 K-sz_u=0 时（K 即题面中的 K），可以发现 f_v=g_v
3、其他情况，即 sz_u\neq 0 且 K-sz_u\neq 0 时，发现 f_v=f_u

那么，更新完 f 之后，我们就要考虑如何更新最长链和次长链了

这也是本题最烦的地方了

依旧分类讨论，依旧是上面三类（这里编号就代表上面的情况）

1、这种情况可以发现 len_v=len_u+w_{u\rightarrow v}，很简单
2、这种情况很容易发现完全没有必要更新
3、最烦的情况来了，这种情况下我们还要分类讨论
1）当 len_u+w\ge len_v 且 id_u\neq v 时，说明 u 的最长链可以更新 v 的最长链，那么直接更新即可
2）当 len_u+w\ge len_v 且 id_u= v 时，说明虽然 u 的最长链的长度可以更新 v，但是若更新了这就不是一条链了，所以也不可以来更新
3）当 slen_u+w\ge len_v 时，说明 u 的次长链可以用来更新 v 的最长链，直接更新即可
4）当 len_u+w\ge slen_v 且 id_u\neq v 时，说明 u 的最长链可以更新 v 的次长链，直接更新即可
5）当 len_u+w\ge slen_v 且 id_u= v 时，这时与2）同理，不可以更新
6）当 slen_u+w\ge slen_v 时，说明 u 的次长链可以更新 v 的次长链，直接更新即可

到这里，第二次dfs就做完了

贴个代码：

void dp(int u,int fa)
{
    for(int i=Head[u];i;i=Edge[i].next)
    {
        int v=Edge[i].to,w=Edge[i].val;
        if(v==fa)continue;
        if(!sz[v])f[v]=f[u]+2*w,len[v]=len[u]+w;//对应1
        else if(K-sz[v])//对应3
        {
            f[v]=f[u];
            if(id[u]!=v&&len[v]<len[u]+w)//对应1）
                slen[v]=len[v],len[v]=len[u]+w,id[v]=u;
            else if(len[v]<slen[u]+w)//对应3）
                slen[v]=len[v],len[v]=slen[u]+w,id[v]=1;
            else if(slen[v]<len[u]+w&&id[u]!=v)//对应4）
                slen[v]=len[u]+w;
            else if(slen[v]<slen[u]+w)//对应6）
                slen[v]=slen[u]+w;
        }
        else f[v]=g[v];//对应2
        dp(v,u);
    }
}

接下来，这题就可以愉快的AC啦，记得开long long就行啦

完整的无注释代码：

#include<bits/stdc++.h>
#define MAXN 500010
#define int long long
using namespace std;
int n,K;
struct Node{int to,next,val;}Edge[MAXN<<1];
int Head[MAXN],cnt_Edge;
void Add_Edge(int u,int v,int w){Edge[++cnt_Edge]={v,Head[u],w};Head[u]=cnt_Edge;}
int pos[MAXN];
int sz[MAXN],g[MAXN],f[MAXN];
int len[MAXN],id[MAXN],slen[MAXN];
void dfs(int u,int fa)
{
    if(pos[u])sz[u]=1;
    for(int i=Head[u];i;i=Edge[i].next)
    {
        int v=Edge[i].to,w=Edge[i].val;
        if(v==fa)continue;
        dfs(v,u);
        if(sz[v])
        {
            g[u]+=g[v]+2*w;
            int now=len[v]+w;
            if(now>=len[u])slen[u]=len[u],len[u]=now,id[u]=v;
            else if(now>slen[u])slen[u]=now;
        }
        sz[u]+=sz[v];
    }
}
void dp(int u,int fa)
{
    for(int i=Head[u];i;i=Edge[i].next)
    {
        int v=Edge[i].to,w=Edge[i].val;
        if(v==fa)continue;
        if(!sz[v])f[v]=f[u]+2*w,len[v]=len[u]+w;
        else if(K-sz[v])
        {
            f[v]=f[u];
            if(id[u]!=v&&len[v]<len[u]+w)
                slen[v]=len[v],len[v]=len[u]+w,id[v]=u;
            else if(len[v]<slen[u]+w)
                slen[v]=len[v],len[v]=slen[u]+w,id[v]=1;
            else if(slen[v]<len[u]+w&&id[u]!=v)
                slen[v]=len[u]+w;
            else if(slen[v]<slen[u]+w)
                slen[v]=slen[u]+w;
        }
        else f[v]=g[v];
        dp(v,u);
    }
}
signed main()
{
    scanf("%lld%lld",&n,&K);
    for(int i=1;i<n;i++)
    {
        int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
        Add_Edge(u,v,w);Add_Edge(v,u,w);
    }
    for(int i=1;i<=K;i++){int x;scanf("%lld",&x);pos[x]=1;}
    dfs(1,0);f[1]=g[1];dp(1,0);
    for(int i=1;i<=n;i++)printf("%lld\n",f[i]-len[i]);
    return 0;
}