题解 P6419 【[COCI2014-2015#1] Kamp】

_CHO · 2020-06-19 18:12:41 · 题解

第二次提交了，认真进行了排版，求管理大大给过/kk

第一次交的时候时间比较紧，于是就没怎么对变量使用Latex，然后就被认真负（du)责(liu)的管理员给乱棍打回来了/kk

以下是原题解

明天就SX AFO了交篇题解%一下

这题大概是我第一道有独立思考切掉的紫题

之前的都是~~各种抄~~借鉴题解

为什么写这题的题解呢?另一个重要的原因是这样的↓

翻了翻已有题解中的几篇，下面几种情况屡见不鲜

样例2都过不去~~论题解是如何过审的~~
变量名不统一，有一些小的笔误
疯狂的防作弊系统，复制编译试图对拍然鹅数十行报错

正因如此，本蒟蒻想道自己写一篇题解，尽量保证不出现上面的错误，如果依然有笔误请轻喷

因为作者忙着复习颓废，Markdown及Latex会有一点偷懒，敬请谅解

说了一堆废话，下面进入正题

树形dp+换根

两遍dfs

这俩思想应该还是比较容易想到，像~~这种暴力搞不了的树上问题一看就是dp~~，再一个题目要求每一个点的情况，暴力跑一定会爆炸，所以需要用到换根

观察题目性质

问题可以简化成，在某一节点i聚会时，此时的答案即为司机把所有人送回家再返回该点的距离减掉从点i到最远的人的家的距离。
如果我们走的是简单路径（不知道简单路径是什么的可以当场AFO了），那么是不存在所谓的最短路的，因为这是一棵树，先送道远的和先送道近的没有本质区别

下面我们来设计状态

首先我们以1号节点为根

$f[u]$ 从点$u$出发把所有人出发并返回$u$的距离 $len[u]$ 从$u$出发，在$u$的子树内，距离$u$最远的那个人的家到$u$的距离 $dlen[u]$ 从$u$出发，在$u$的子树内，距离$u$次远第~~二远~~的那个人的家到$u$的距离 $up[u]$ 不在u的子树内，距离$u$最远的那个人的家到$u$的距离 $siz[u]$ $u$及$u$的子树内有多少个人的家则最终的答案应为 $ans[i] = f[i] - max(up[i],len[i] )

那么我们考虑代码

第一次dfs我们主要是处理子树内的问题

我们需要处理出 g[],len[],dlen[]，siz[]

这应该很简单

第二次就是换根操作了

我们需要处理出up[],f[]

我们需要分类讨论，设当前的点为u，父亲节点为fa，这条边的边权为 _w

当所有人的家都在u的子树内即siz[u]=k时，这时候f[u]即是g[u]，而up[u]应当是0，这很显然，因为u的子树外没有家
当所有人的家都不在u的子树内即siz[u]=0时，这是f[u]=f[fa]+2_w,因为你首先要走到父亲节点这样才能送人回家，up[u]则完全由父亲节点更新（详见代码）
- 当$u$在他父亲的$len[fa]$上时，$up[u]$就需要从$dlen[fa]$更新过来~~因为$len[fa]$要经过$u$~~

当u不在父亲的len[fa]上时，同理由len[fa]转移过来

讲的比较抽象，建议画图+阅读代码理解

~~十年OI一场空，不开long long见祖宗~~

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e+5+100;
struct Edge{
    int v;
    ll w;
};
int n,k;
int he[maxn],ne[maxn<<1],cnt=1;
Edge G[maxn<<1];
bool p[maxn];
int siz[maxn];
ll f[maxn],g[maxn],up[maxn],len[maxn],dlen[maxn];

void add_Edge(int u,int v,ll w){
    G[cnt].v = v;
    G[cnt].w = w;
    ne[cnt] = he[u];
    he[u] = cnt++;
}
void dfs(int u,int fa){
    siz[u] = p[u];
    for(int i=he[u];i;i=ne[i]){
        int v=G[i].v;
        int w=G[i].w;
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]){
            g[u] += g[v] + 2*w;
            if(len[v]+w>len[u]){
                dlen[u] = len[u];
                len[u] = len[v] + w;
            }
            else if(len[v]+w>dlen[u]){
                dlen[u] = len[v] + w;
            }
        }
    }
}
void dfs(int u,int fa,ll _w){
    if(siz[u]==k){
        f[u] = g[u];
        up[u] = 0;
    }
    else if(siz[u]==0){
        f[u] = f[fa] + 2*_w;
        up[u] = max(up[fa],len[fa]) + _w;
    }
    else{
        f[u] = f[fa];
        if(len[fa]-len[u]==_w) up[u] = max(up[fa],dlen[fa]) + _w;
        else up[u] = max(up[fa],len[fa]) + _w;
    }
    for(register int i=he[u];i;i=ne[i]){
        int v=G[i].v;
        int w=G[i].w;
        if(v==fa) continue;
        dfs(v,u,w);
    }
}
int main(){
    cin>>n>>k;
    for(register int i=1;i<n;++i){
        int u,v;
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        add_Edge(u,v,w);
        add_Edge(v,u,w);
    }
    for(register int i=1;i<=k;++i){
        int x;
        scanf("%d",&x);
        p[x] = true;
    }
    dfs(1,0);
    dfs(1,0,0);
    for(register int i=1;i<=n;++i) printf("%lld\n",f[i]-max(up[i],len[i]));
    return 0;
}