P6419 COCI2014-2015#1 Kamp

换根 \(dp\) 的 trick。

题面

钦定 \(k\) 个关键点，求每个点出发，访问完所有关键点的距离最小值。

思路

设 \(g_u\) 为从点 \(u\) 出发，访问完子树内所有关键点后，回到点 \(u\) 的距离最小值。

\(s_u\) 为点 \(u\) 子树内关键点个数，\(E(u,v)\) 为边权。

自然我们需要换根 dp 求出每个点作为根的时候的 \(g_u\)，设这个答案为 \(f_u\)​​。

\(f\) 为 \(u\) 的父亲。

考虑换根转移：

1. 若 \(s_u=0\)，则 \(f_u=g_f+E(f,u)\times 2\)，画图显而易见。
2. 若 \(k-s_u=0\)，则 \(f_u=g_u\)，都在 \(u\) 的子树内，也显而易见。
3. 其他情况，则 \(f_u=f_f\)，把 \(u\) 作为根，仔细观察一下我们更新的递推式，你会发现 \(f_u=f_f-(g_u-E(u,f))+(g_u+E(u,f))\)，化简即可得。

由于车开到最后一个关键点可以不返回 \(u\) 点，而最小访问距离是可以有多重解法的，肯定存在一种方案使得最后访问最距离 \(u\) 最远的点，这样就可以剩下最大距离不用返回 \(u\)​​ 点。

下文所述的最长链，次长连均为关键点作为链的一端的链。

这个貌似可以使用 dfn 序+线段树维护最长链，单次查询复杂度 \(O(\log n)\)，但这里也可以利用换根 dp 求最长链。

下面是利用换根 dp 求最长链的思路。

设 \(u\) 子树内到 \(u\) 的最长链长度为 \(len_u\)，来自 \(u\) 的儿子 \(id_u\)。

设 \(u\) 子树内到 \(u\) 的次长链长度为 \(slen_u\)，要求与 \(len_u\) 来自的儿子不相同。

\(v\) 为 \(u\) 的儿子，有转移：

1. 若 \(len_u<len_v+E(u,v)\)，则 \(slen_u\gets len_u,len_u\gets len_v+E(u,v),id_u\gets v\)。
2. 若不满足 1 且 \(slen_u<len_v+E(u,v)\)，则 \(slen_u\gets len_v+E(u,v)\)​。

变换 \(len_u\) 的意义为到 \(u\) 点的最长链，\(slen_u\) 的意义为和 \(len_u\) 来自不同的 \(u\)​ 所相接的边的次长链。

易得根的 \(len\) 与 \(slen\) 为原来的值。

设 \(f\) 为 \(u\) 的父亲，考虑从根开始的换根转移：

1. 若 \(len_u<len_f+E(u,f)\) 且 \(id_f\neq u\)，则 \(slen_u\gets len_u,len_u\gets len_f+E(u,f),id_u\gets f\)。
2. 若 \(len_u<slen_f+E(u,f)\)，则 \(len_u\gets slen_f+E(u,f),id_u\gets -1\)，此时​无论 \(id_u\) 取何值，都不影响下一步转移。
3. 若 \(slen_u<len_f+E(u,f)\) 且 \(id_f\neq u\)，则 \(slen_u\gets len_f+E(u,f)\)​。
4. 若 \(slen_u<slen_f+E(u,f)\)，则 \(slen_u\gets slen_f+E(u,f)\)。

满足上述转移中最靠前的一条，便可以退出转移。

到这里我们变可以输出答案 \(f_i-len_i\)。

CODE

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn=5e5+5;

struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt,val;}edge[maxn*2];
    inline void add(int x,int y,int z)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        edge[tot].val=z;
        head[x]=tot;
    }
}T;

int n,k;
int s[maxn],id[maxn];

ll dp[maxn],f[maxn],len[maxn],slen[maxn];

inline int Max(int a,int b)
{
    if(a<b) return b;
    else return a;
}
inline void dfs_fir(int u,int fa)
{
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to;
        if(v==fa) continue;
        dfs_fir(v,u);s[u]+=s[v];
    }
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to,w=T.edge[i].val;
        if(v==fa) continue;
        if(!s[v]) continue;
        dp[u]+=dp[v]+w*2;
        if(len[v]+w>=len[u]) slen[u]=len[u],len[u]=len[v]+w,id[u]=v;
        else if(len[v]+w>=slen[u]) slen[u]=len[v]+w;
    }
}
inline void dfs_sec(int u,int fa)
{
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to,w=T.edge[i].val;
        if(v==fa) continue;
        if(!s[v]) f[v]=f[u]+w*2,len[v]=len[u]+w;
        else if(k-s[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(id[u]!=v&&slen[v]<len[u]+w) slen[v]=len[u]+w;
            else if(slen[v]<slen[u]+w) slen[v]=slen[u]+w;
        }
        else f[v]=dp[v];
        dfs_sec(v,u);
    }
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        T.add(x,y,z),T.add(y,x,z);
    }
    for(int i=1;i<=k;i++)
    {
        int x;
        scanf("%d",&x);
        s[x]=1;
    }
    dfs_fir(1,0);
    f[1]=dp[1];
    dfs_sec(1,1);
    for(int i=1;i<=n;i++) printf("%lld\n",f[i]-len[i]);
}

后记

这个 trick 相较于数据结构优势在于可以 \(O(1)\)，劣势在于不可以在线。