首页 > 其他 > 详细

「HDU-2196」Computer (树形DP、树的直径)

时间:2020-09-29 23:24:17      阅读:5      评论:0      收藏:0      [点我收藏+]

标签:方式   一次   难点   clear   inline   spa   

「HDU-2196」Computer
树形dp,树的最长路径(最远点对)

题意

给出一棵nn个结点的无根树,求出每个结点所能到达的最远点的距离。

解法

将无根树转成有根树,并进行两次DFS。

  1. 第一次DFS求出每个结点在其子树中的正向最大距离正向次大距离,记为dp[0][x]dp[1][x],并标记最长距离所对应的子结点id[i] ,利用id[i]能跳过最大点计算第二大的点;

    此时可知对于每个结点ii,最远点的距离只有两种可能:

    • 结点\(i\)正向最大距离
    • 结点\(i\)链接其父结点所能到达的最大距离,即反向最大距离
  2. 第二次DFS求出反向最长距离

    • 由上步我们获得了正向最大距离,正向次大距离和最大距离的儿子节点标记。画图可以知道我们建立的这棵树,i节点的最远距离只有两种选择:i节点所在子树的最大距离,或者i节点连接它的父节点所能到达的最大距离。(即前者往下走,后者先往上走之后很可能也往下走)
    • 所以我们只要求出*反向最大距离*dist[i][2](即i节点往它的父节点走所能到达的最大距离)就可以知道i节点在整个树中能走的最大距离了。
    • dist[i][2]求法:i节点往它的父节j点走,如果它的父节点的正向最大距离不经过i的话,那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向最大距离+ W[i][j].
    • 如果它的父节点的正向最大距离经过i的话,那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向次大距离+ W[i][j].
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 100;
int n, dp[3][N], id[N];
vector<int>p[N], val[N];
void dfs1(int x,int f) {//第一个dfs更新子树的最大跟次大和s
	for (int i = 0; i < p[x].size(); i++){
		int to = p[x][i];
		if (to == f) continue;
		dfs1(to, x);
		if (dp[0][x] < dp[0][to] + val[x][i]) //这里是更新最大和,记住经过哪个儿子最大
		{
			dp[0][x] = dp[0][to] + val[x][i];
			id[x] = to;
		}
	}
	for (int i = 0; i < p[x].size(); i++){
		int to = p[x][i];
		if (to == f) continue;
		if (id[x] == to) continue;  //跳过这个儿子,再剩下点里面找一个最大的,就是这个点次大的
		dp[1][x] = max(dp[1][x], dp[0][to] + val[x][i]);
	}
}
void dfs2(int x,int f) {//这个是更新先往父亲节点走一步的最大和
	for (int i = 0; i < p[x].size(); i++){
		int to = p[x][i];
		if (to == f) continue;
		if (to == id[x])  //难点,每个父亲都有两种方式,一个是再往父亲走一步,一个是走父亲的子树,max(dp[2][x], dp[1][x]),这个就体现出这两部了,注意经不经过这个点直接走子树最大和的那个点
			dp[2][to] = max(dp[2][x], dp[1][x]) + val[x][i];  //这个是针对儿子,所以是dp[2][to] = ,体现了先走一步父亲,经过就走次大的,再走最大的就重复了一段
		else
			dp[2][to] = max(dp[2][x], dp[0][x]) + val[x][i];
		dfs2(to, x);  //因为dfs1更新了所有子树的特点,子树的信息可以直接用了,父节点的信息从一步步dfs下去都已经更新好了,上面的也是可以直接用,每一步都看看是不是走父亲的父亲更好,一直更新最优
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	while (cin >> n) {
		memset(dp, 0, sizeof dp);
		for (int i = 0; i <= n; ++i)val[i].clear(), p[i].clear();
		for (int i = 2; i <= n; ++i) {
			int a, b; cin >> a >> b;
			p[i].push_back(a);
			val[i].push_back(b);
			p[a].push_back(i);
			val[a].push_back(b);
		}
		dfs1(1, -1);
		dfs2(1, -1);
		for (int i = 1; i <= n; ++i)
			cout << max(dp[0][i], dp[2][i]) << endl;
	}
}

「HDU-2196」Computer (树形DP、树的直径)

标签:方式   一次   难点   clear   inline   spa   

原文:https://www.cnblogs.com/RioTian/p/13751877.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号