C/C++教程

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

本文主要是介绍[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-从根出发的最长链。
image
如上图，点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]);
	}
}
这篇关于[oiclass2478] Kamp：树形DP+换根+最长链的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航