[oiclass2478] Kamp:树形DP+换根+最长链

题意

一颗树 \(n\) 个点,\(n-1\) 条边,经过每条边都要花费一定的时间,任意两个点都是联通的。
有 \(K\) 个人(分布在 \(K\) 个不同的点)要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发,把这 \(K\) 个人分别送回去。
请你回答,对于 \(i=1\sim n\),如果在第 \(i\) 个点举行聚会,司机最少需要多少时间把 \(K\) 个人都送回家。

数据范围

\(K \leq N \leq 500000\)
\(1 \leq x,y \leq N, 1 \leq z \leq 1000000\)

题解

对于本题,考虑以1为根的情况的解法,显然,答案等价于从根出发到各个点的边权和*2-从根出发的最长链。
[oiclass2478] Kamp:树形DP+换根+最长链
如上图,点3和点7为需要送达的点,从根1出发到达点3和点7的边权和为\(4+2+3+1=10\),从根1出发到达点3或者点7的最长链是\(1\rightarrow 2\rightarrow 4 \rightarrow 7\),其值为\(4+2+3=9\),所以从根1出发所需的时间为\(10*2-9=11\)

明白以上解法后,我们需要以每个点为根求出所需的最少时间,这时,我们就需要用到换根的思想了。
这里有两个性质需要换根
1、设从根u出发需要到达的各个指定点的边权和为len[u],那么,从根u转移到儿子v时,其边权和会如何转移呢?如果v在原有指定点的必经路上,则权值不变,即len[v]=len[u];如果所有指定点在v的下方,则len[v]=len[u]-w(w为u到v的边权),即少走了w这条边;如果v下方不包含任何指定点,则len[v]=len[u]+w,即多走了w这条边。

2、利用树形DP的思想求出最长链,根u的最长链为dis1[u],次长链为dis2[u],现在要从u转移到儿子v,其最长链如何转移呢?v所在子树的最长链为dis1[v],v子树之外的最长链为dis1[u]+w(w为u到v的边权),这里需要特判dis1[u]是否包含v,细节见代码。比较两者的值,即可更新dis1[v]的值为max(dis1[v],dis1[u]+w)。

代码

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=500000+5;
struct edge{
	int x,y,z;
};
vector<edge> g[N];
int n,k,has[N],sz[N],son[N];
long long dis1[N],dis2[N],len[N];
void dfs(int u,int fa){
	if(has[u]==1)sz[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].y;
		int w=g[u][i].z;
		if(v==fa)continue;
		dfs(v,u);
		sz[u]+=sz[v];
		len[u]+=len[v];
		if(sz[v]==0)continue;
		len[u]+=w;
		if(dis1[v]+w>dis1[u]){
			dis2[u]=dis1[u];
			dis1[u]=dis1[v]+w;
			son[u]=v;
		}else{
			if(dis1[v]+w>dis2[u]){
				dis2[u]=dis1[v]+w;
			}
		}
	}
}
void dp(int u,int fa){
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].y;
		int w=g[u][i].z;
		if(v==fa)continue;
		
		len[v]=len[u];
		if(sz[v]==0)len[v]+=w;
		if(sz[v]==k)len[v]-=w;
		
		long long out_dis=(son[u]==v?dis2[u]:dis1[u])+w;
		if(out_dis>dis1[v]){
			dis2[v]=dis1[v];
			dis1[v]=out_dis;
			son[v]=u;
		}else{
			if(out_dis>dis2[v]){
				dis2[v]=out_dis;
			}
		}
		dp(v,u);
	}
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1,x,y,z;i<n;i++){
		scanf("%d %d %d",&x,&y,&z);
		g[x].push_back((edge){x,y,z});
		g[y].push_back((edge){y,x,z});
	}
	for(int i=1,x;i<=k;i++){
		scanf("%d",&x);
		has[x]=1;
	}
	dfs(1,-1);
	dp(1,-1);
	for(int i=1;i<=n;i++){
		printf("%lld\n",len[i]*2-dis1[i]);
	}
}
上一篇:计数学习小记


下一篇:AGC056 题解