洛谷 P6419 COCI2014/2015 #1 Kamp 题解

题意

一颗树 $n$ 个点，$n-1$ 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。

有 $k$ 个人（分布在 $k$ 个不同的点）要集中到一个点举行聚会。

聚会结束后需要一辆车从举行聚会的这点出发，把这 $K$ 个人分别送回去。

请你回答，对于 $i=1\sim n$ ，如果在第 $i$ 个点举行聚会，司机最少需要多少时间把 $k$ 个人都送回家。

$1\le k\le n\le 5\times 10^5$，$1\le x,y\le n$，$1\le z\le 10^8$ 。

思路

这是一道换根dp

直接计算从一个点出发，经过所有家之后最后在一个点停下的最短路程，是比较难的。但是可以维护从一个点出发，再回到自己的最短路程，减去该点到其中一个家的最长链，那也是答案。

第一个dfs

经典地，先用第一个dfs处理子树内信息。

用$vi{s}_u$标记$u$是否为一个家，$s{v}_u$表示$u$子树内有多少有家之人。

令$g_u$表示，在$u$子树内，从$u$出发走完所有有家之人再回到$u$的最短距离，那么在处理边$(u,v)$，边权为$w$时，有：
$$g_u=2w+\sum _{v\in so{n}_u}{g}_v$$

$w$要乘$2$是因为要走来回。

那么到维护最长链了，先维护子树内的最长链；不过为了在第2次dfs中，处理全局的最长链信息，涉及到两个点$(u,v)$的次序问题（即$u$成为$v$子树内的一点），还需要维护一个次长链来保证正确性。

令$D_u$表示$u$节点开始子树内最长链，$s{D}_u$表示$u$节点开始子树内次长链；可以用一个$n{x}_u$记录该最长链上，$u$的下一个节点（因为在最长链上任一节点$x$子树的、由$x$开始的最长链，必然与$u$开始的最长链重合）

void dfs1(ll u,ll fa)
{if(vis[u])sv[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;dfs1(v,u);if(sv[v]){g[u]+=g[v]+2*w;if(w+D[v]>=D[u]){sD[u]=D[u];D[u]=w+D[v];nx[u]=v;}else if(w+D[v]>sD[u])sD[u]=w+D[v];}sv[u]+=sv[v];} 
}

第二个dfs

在第二个dfs中，我们将处理整棵树内的信息了。

令$f_u$表示，在整棵树中，从$u$出发走完所有有家之人再回到自己的最短路程。

在第一个dfs中，我们记录了$s{v}_u$表示$u$子树内有多少有家之人；对于一个节点$u$和后继结点$v$，考虑利用$s{v}_u$或$s{v}_v$进行分类讨论：

$s{v}_v=k$

那么和子树的情况没有区别，也不必更新最长链、次长链了，直接$f_v=g_v$即可。

$s{v}_v=0$

那么说明$v$的子树内没有人有家，在第一次dfs时$u$并没有往$v$的方向更新。此处可以看作$u$是在$v$的子树内，需要倒着用$u$来更新$v$。（并且可以直接更新，比大小都可以不需要qwq）

其余情况

$u$和$v$子树内都有有家之人。设最长链分布如图所示：

设$w$为边$(u,v)$的边权

更新$D_v$

若$D_u+w\ge D_v$且$n{x}_u\ne v$（即$v$不在$u$的原本的最长链上），直接更新$D_v$，若$n{x}_u=v$则不能更新。

若$s{D}_u+w\ge D_v$，并没有影响，直接继承即可。

更新$s{D}_v$

与上相同

void dfs2(ll u,ll fa)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;if(!sv[v])//v子树内无家，倒着更新 {if(D[u]+w>=D[v]){sD[v]=D[v];D[v]=D[u]+w;f[v]=f[u]+2*w;}	}else if(k-sv[v]==0)f[v]=g[v];else //更新D(v) {f[v]=f[u];if(D[u]+w>=D[v]&&nx[u]!=v){sD[v]=D[v];D[v]=D[u]+w;nx[v]=u;}else if(sD[u]+w>=D[v]){sD[v]=D[v];D[v]=sD[u]+w;nx[v]=u;}else if(D[u]+w>=sD[v]&&nx[u]!=v)sD[v]=D[u]+w;else if(sD[u]+w>=sD[v])sD[v]=sD[u]+w;}dfs2(v,u);}
}

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+9;
ll n,k;
ll idx,head[N];
ll sv[N],vis[N],D[N],sD[N],nx[N],f[N],g[N];
//sv(u):u子树内总共多少有家之人
//D/sD(u):u起点最长次长链
//nx(u): 最长链上下一个节点
//g(u):u子树内走完所有有家之人回u的最短距离
//f(u):整棵树内走完所有有家之人回u的最短距离
struct edge
{ll to,next,w;
}e[N<<1];
void addedge(ll u,ll v,ll w)
{idx++;e[idx].to=v;e[idx].next=head[u];e[idx].w=w;head[u]=idx;
}
void dfs1(ll u,ll fa)
{if(vis[u])sv[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;dfs1(v,u);if(sv[v]){g[u]+=g[v]+2*w;if(w+D[v]>=D[u]){sD[u]=D[u];D[u]=w+D[v];nx[u]=v;}else if(w+D[v]>sD[u])sD[u]=w+D[v];}sv[u]+=sv[v];} 
}
void dfs2(ll u,ll fa)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;if(!sv[v])//v子树内无家，倒着更新 {if(D[u]+w>=D[v]){sD[v]=D[v];D[v]=D[u]+w;f[v]=f[u]+2*w;}	}else if(k-sv[v]==0)f[v]=g[v];else //更新D(v) {f[v]=f[u];if(D[u]+w>=D[v]&&nx[u]!=v){sD[v]=D[v];D[v]=D[u]+w;nx[v]=u;}else if(sD[u]+w>=D[v]){sD[v]=D[v];D[v]=sD[u]+w;nx[v]=u;}else if(D[u]+w>=sD[v]&&nx[u]!=v)sD[v]=D[u]+w;else if(sD[u]+w>=sD[v])sD[v]=sD[u]+w;}dfs2(v,u);}
}
int main()
{scanf("%lld%lld",&n,&k);for(int i=1;i<n;i++){ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);}for(int i=1;i<=k;i++){ll u;scanf("%lld",&u);vis[u]=1;}dfs1(1,0);f[1]=g[1];dfs2(1,0);for(int i=1;i<=n;i++)printf("%lld\n",f[i]-D[i]);return 0;
}