题意：给你一棵树，你可以把某条边的边权变为0，然后选一个点，使得所有点到这个点的距离和最小。
思路：之前做过一道题没有变为0的操作，那道题直接求直径就可以，这道题比较麻烦，网上看了半天，，，
首先我们先dfs一遍求出来点1的答案，设dp[i][0][1]为以i为根的最长路径的最小长度，考虑对于相邻两个点u, v ， 我们可能会删除u, v 之间的边或者之前就将边删除了然后加上w[u][v]，所以dp[u][0][1] = min(dp[v][0][0], max(dp[v][0][1], dp[v][1][0]) + w[u][v])。
接着我们考虑换根的影响，用f[i][2] 记录一下当前节点与父节点间在哪删除边的答案，f[i][0]是来源于i的父节点方向最长距离和父节点的子树的最长距离取max再加上i和父节点的边权。如果次长距离是点i的话我们就需要维护第三长的距离。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103#include <bits/stdc++.h> using namespace std; typedef long long ll; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1|1 const int maxn = 2e5 + 10; const int inf = 0x3f3f3f3f; vector<pair<int, int> > e[maxn]; //邻接点，权值 pair<int, int> dp[maxn][3][2]; //dp[i][j][k]：i：以i为根 ，j：0表示最长 1表示次长 2表示第3长 ，k：1带修改 0不带修改 int f[maxn][2], d[maxn]; //f[i][2]表示父节点换根的最大路径长度(修改/不修改) int ans, id; void init(int n) { ans = inf, id = n; for(int i = 1; i <= n; ++i) { e[i].clear(); memset(dp[i], 0, sizeof(dp[i])); //first是答案，second是结点 memset(f[i], 0, sizeof(f[i])); d[i] = 0; } } void dfs(int u, int fa) { for(auto x : e[u]) { int v = x.first; if(v == fa) continue; dfs(v, u); d[v] = x.second; if(dp[v][0][0].first + d[v] >= dp[u][0][0].first) //维护三个最大 { dp[u][2][0] = dp[u][1][0]; dp[u][1][0] = dp[u][0][0]; dp[u][0][0] = make_pair(dp[v][0][0].first + d[v], v); } else if(dp[v][0][0].first + d[v] >= dp[u][1][0].first) { dp[u][2][0] = dp[u][1][0]; dp[u][1][0] = make_pair(dp[v][0][0].first + d[v], v); } else if(dp[v][0][0].first + d[v] >= dp[u][2][0].first) dp[u][2][0] = make_pair(dp[v][0][0].first + d[v], v); } int v = dp[u][0][0].second; //更新带修改的值 dp[u][0][1].first = min(dp[v][0][0].first, max(dp[v][0][1].first, dp[v][1][0].first) + d[v]); v = dp[u][1][0].second; dp[u][1][1].first = min(dp[u][0][0].first, max(dp[v][0][1].first, dp[v][1][0].first) + d[v]); } void dfs2(int u, int fa) //换根 { int tmp1 = max(dp[u][0][1].first, dp[u][1][0].first), tmp2 = max(dp[u][0][0].first, f[u][1]); int res = min(max(tmp1, f[u][0]), tmp2); if(res < ans) ans = res, id = u; else if(res == ans) id = min(id, u); for(auto x : e[u]) { int v = x.first; if(v == fa) continue; if(v == dp[u][0][0].second) { f[v][0] = max(dp[u][1][0].first, f[u][0]) + x.second; f[v][1] = min(max(dp[u][1][0].first, f[u][0]), min(max(f[u][0], max(dp[u][1][1].first, dp[u][2][0].first)), max(dp[u][1][0].first, f[u][1])) + x.second); } else { f[v][0] = max(dp[u][0][0].first, f[u][0]) + x.second; if(dp[u][1][0].second == v) //如果修改同一个地方 f[v][1] = min(max(dp[u][0][0].first, f[u][0]), min(max(f[u][0], max(dp[u][0][1].first, dp[u][2][0].first)), max(dp[u][0][0].first, f[u][1])) + x.second); else f[v][1] = min(max(dp[u][0][0].first, f[u][0]), min(max(f[u][0], max(dp[u][0][1].first, dp[u][1][0].first)), max(dp[u][0][0].first, f[u][1])) + x.second); } dfs2(v, u); } } int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); init(n); for(int i = 1; i < n; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); e[u].push_back({v, w}); e[v].push_back({u, w}); } dfs(1, -1); ans = max(dp[1][0][1].first, dp[1][1][0].first); dfs2(1, -1); printf("%d %dn", id, ans); } return 0; }
最后
以上就是美好戒指最近收集整理的关于HDU 6613 Squrirrel【树形DP + 换根】的全部内容，更多相关HDU内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复