2019 杭电多校第三场 HDU - 6613 Squrirrel 树形dp 某边为0时的重心

题目链接：https://cn.vjudge.net/problem/HDU-6613

题意：一棵树，可以使一条边权值变为0，求树的重心以及最远距离

题解：这应该是写的最长的树形dp了，可能写的有点麻烦了。

dp[i][j] 表示i 这个节点的子树中第 j 长的距离，id[i][j] 记录这个儿子的编号，va[i][j] 记录和儿子连接的这条边的权值

an[i][j] 表示 i 这个节点的子树使得j条边变为0的最长距离，

an[u][0] = dp[u][0];
an[u][1] = max(dp[u][1], min(an[id[u][0]][0], an[id[u][0]][1] + 连接儿子的边权));

pre[i][j] 表示第二次dfs时，i 节点上面那个分支，使得 j 条边变为0的最长距离

第一次dfs很简单，把每个分支前3大的处理出来

第二次dfs就开始求每个点对应的结果了，首先子树中已经处理出来了，然后就是通过父亲来更新孩子的上面那个分支了，如果该节点是父亲最长的，那么就是父亲的第二长的和父亲上面分支 中较大的求个优解，如果是第二大的分支中某边变为0，这个时候第三大的也就需要考虑了，对应如果不是父亲最长的，方法类似。思路挺好想，就是处理起来有点复杂。。。。

#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
#define INF 0x3f3f3f3f
struct edge {
int to, w, nex;
}e[N * 2];
int n;
int dp[N][3], pre[N][2], id[N][3], va[N][3];
int an[N][2];
int head[N], len;
void init() {
for(int i = 0; i <= n; i++) {
head[i] = -1;
dp[i][0] = dp[i][1] = 0;
pre[i][0] = pre[i][1] = 0;
}
len = 0;
}
void addedge(int x, int y, int z) {
e[len].to = y;
e[len].w = z;
e[len].nex = head[x];
head[x] = len++;
}
void dfs1(int u, int fa) {
int to, pos = -1;
for(int i = head[u]; i != -1; i = e[i].nex) {
to = e[i].to;
if(to == fa) continue;
dfs1(to, u);
if(dp[u][0] < dp[to][0] + e[i].w) {
dp[u][2] = dp[u][1];
id[u][2] = id[u][1];
va[u][2] = va[u][1];
dp[u][1] = dp[u][0];
id[u][1] = id[u][0];
va[u][1] = va[u][0];
dp[u][0] = dp[to][0] + e[i].w;
id[u][0] = to;
va[u][0] = e[i].w;
pos = e[i].w;
} else if(dp[u][1] < dp[to][0] + e[i].w) {
dp[u][2] = dp[u][1];
id[u][2] = id[u][1];
va[u][2] = va[u][1];
dp[u][1] = dp[to][0] + e[i].w;
id[u][1] = to;
va[u][1] = e[i].w;
} else if(dp[u][2] < dp[to][0] + e[i].w) {
dp[u][2] = dp[to][0] + e[i].w;
id[u][2] = to;
va[u][2] = e[i].w;
}
}
an[u][0] = dp[u][0];
if(pos != -1) an[u][1] = max(dp[u][1], min(an[id[u][0]][0], an[id[u][0]][1] + pos));
//	cout << u << " " << an[u][0] << " " << an[u][1] << endl;
}
int ans, ansid;
void dfs2(int u, int fa) {
int to, cnt;
for(int i = head[u]; i != -1; i = e[i].nex) {
to = e[i].to;
if(to == fa) continue;
if(id[u][0] != to) {
pre[to][0] = max(dp[u][0], pre[u][0]) + e[i].w;
pre[to][1] = max(dp[u][0], pre[u][0]);
cnt = max(pre[u][1], dp[u][0]) + e[i].w;
if(id[u][1] != to) cnt = min(cnt, max(max(pre[u][0], min(an[id[u][0]][1] + va[u][0] , an[id[u][0]][0])), dp[u][1]) + e[i].w);
else cnt = min(cnt, max(max(pre[u][0], min(an[id[u][0]][1] + va[u][0] , an[id[u][0]][0])), dp[u][2]) + e[i].w);
pre[to][1] = min(pre[to][1], cnt) ;
} else {
pre[to][0] = max(dp[u][1], pre[u][0]) + e[i].w;
pre[to][1] = max(dp[u][1], pre[u][0]);
cnt = max(pre[u][1], dp[u][1]) + e[i].w;
cnt = min(cnt, max(max(pre[u][0], min(an[id[u][1]][1] + va[u][1] , an[id[u][1]][0])), dp[u][2])+ e[i].w) ;
pre[to][1] = min(pre[to][1], cnt);
}
//
cout << to << " " << pre[to][0] << " " << pre[to][1] << " " << an[to][0] << " " << an[to][1] << endl;
if( min(max(pre[to][1], dp[to][0]), max(pre[to][0], an[to][1])) < ans || (min(max(pre[to][1], dp[to][0]), max(pre[to][0], an[to][1])) == ans && to < ansid)) {
ans = min(max(pre[to][1], dp[to][0]), max(pre[to][0], an[to][1]));
ansid = to;
}
dfs2(to, u);
}
}
int main() {
int T, x, y, z;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
init();
for(int i = 1; i < n; i++) {
scanf("%d %d %d", &x, &y, &z);
addedge(x, y, z);
addedge(y, x, z);
}
dfs1(1, 0);
ans = an[1][1], ansid = 1;
dfs2(1, 0);
printf("%d %dn", ansid, ans);
}
return 0;
}

最后

以上就是成就雪碧为你收集整理的2019 杭电多校第三场 HDU - 6613 Squrirrel 树形dp 某边为0时的重心的全部内容，希望文章能够帮你解决2019 杭电多校第三场 HDU - 6613 Squrirrel 树形dp 某边为0时的重心所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。