HDU 6613 Squrirrel 树形dp

Love The Way You Lie 2023-08-17 17:22 103阅读 0赞

题意：给你一颗树，你可以把这棵树上的一条边的边权变为0，现在让你选一个根，让所有点到这个点的最大距离尽量的小。如果有多个根的最大距离距离相同，输出编号最小的边。

思路：如果没有把边权变为0的操作，这个题实际上是找树的直径的中心。现在有变为0的操作，很容易想到加一维来标记是否已经把某条边的边权变为0。我们不妨先算出以1为根的答案。设dp\[i\]\[0\]是以i为根的子树中没有变边权的最大距离，dp\[i\]\[1\]是把最长的那条路径的某条边边权变为0后的这条最长路径长度的最小值。我们发现只知道最长的路径好像不够，因为最长路径的某条边边权变为0后可能就没次长路径长了。所以我们需要维护一下次长路径。那么我们在第一遍dfs的时候维需要护一下以i为根的子树中的最长路径和次长路径，以及最长路径和次长路径在修改后的最小长度。对于不带修改的最长路径和次长路径，直接维护就行。那么怎么维护修改过的最长路径的最小长度呢？我们需要记录一下到点i的最长路径中和i相邻的点j（j是i的孩子），那么分两种情况：1：把i和j之间的边删除。2：取之前删过的边的最小值加上i和j点之间的边的边权。设dp\[i\]\[0\]\[1\]为以i为根的最长路径（0:最长， 1：次长）（1:带修改, 0:不修改）的最小长度，那么dp\[i\]\[0\]\[1\] = min(dp\[j\]\[0\]\[0\], max(dp\[j\]\[0\]\[1\], dp\[j\]\[1\]\[0\]) + w)。次长路同理可得。那么我们就可以得出以1为根的答案了。ans = min(dp\[1\]\[0\]\[1\], dp\[1\]\[1\]\[0\])。现在考虑用换根法计算以其它点为根的答案，即来自父节点方向的答案的贡献。我们考虑一下父节点对我们的影响。设f\[i\]\[0/1\]为以i为根它的父亲节点方向所形成的路径的的最大长度(带修改/不带修改)，那么我们在计算以i为根的答案时把父节点方向的贡献也考虑在内就行，即考虑是修改i和父节点连的边，还是修改父节点方向的边，还是修改子树的边？这样就把答案计算出来了。怎么维护f\[i\]\[0\]和f\[i\]\[1\]呢？f\[i\]\[0\]肯定来源于i的父节点方向最长距离和父节点的子树的最长距离取max再加上i和父节点的边权。子树的最长距离是不包括i的，所以我们转移的时候要特判一下。那么问题来了，我们的次长距离万一就是点i怎么办？所以我们之前相当于少维护了个第三长的距离，即第一遍dfs时需要维护最长，次长，第三长的距离。f\[i\]\[1\]也一样，考虑枚举修改的哪条边来进行转移(父节点方向的边，子树方向的边)。

代码：

#include <bits/stdc++.h>
    #define pii pair<int, int>
    using namespace std;
    const int maxn = 200010;
    pii dp[maxn][3][2];//点， 第几远，不删边/删边
    int f[maxn][2];//父亲节点来的，不删边/删边
    int d[maxn];
    vector<pii> G[maxn];
    int ans, pos;
    void add(int x, int y, int z) {
    	G[x].push_back(make_pair(y, z));
    	G[y].push_back(make_pair(x, z));
    }
    void dfs1(int x, int fa) {
    	for (auto y : G[x]) {
    		if(y.first == fa) continue;
    		dfs1(y.first, x);
    		d[y.first] = y.second;
    		if(dp[y.first][0][0].first + y.second >= dp[x][0][0].first) {
    			dp[x][2][0] = dp[x][1][0]; 
    			dp[x][1][0] = dp[x][0][0];
    			dp[x][0][0] = make_pair(dp[y.first][0][0].first + y.second, y.first);
    		} else if(dp[y.first][0][0].first + y.second >= dp[x][1][0].first) {
    			dp[x][2][0] = dp[x][1][0];
    			dp[x][1][0] = make_pair(dp[y.first][0][0].first + y.second, y.first);
    		} else if(dp[y.first][0][0].first + y.second >= dp[x][2][0].first) {
    			dp[x][2][0] = make_pair(dp[y.first][0][0].first + y.second, y.first);
    		}
    	}
    	int tmp = dp[x][0][0].second;
    	dp[x][0][1].first = min(dp[tmp][0][0].first, max(dp[tmp][0][1].first, dp[tmp][1][0].first) + d[tmp]);
    	tmp = dp[x][1][0].second;
    	dp[x][1][1].first = min(dp[tmp][0][0].first, max(dp[tmp][0][1].first, dp[tmp][1][0].first) + d[tmp]);
    }
    void dfs2(int x, int fa) {
    	int tmp = min(max(f[x][0], max(dp[x][0][1].first, dp[x][1][0].first)), max(f[x][1], dp[x][0][0].first));
    	if(tmp < ans) {
    		ans = tmp;
    		pos = x;
    	} else if(tmp == ans) {
    		pos = min(pos, x);
    	}
    	for (auto y : G[x]) {
    		if(y.first == fa) continue;
    		if(y.first == dp[x][0][0].second) {
    			f[y.first][0] = max(dp[x][1][0].first, f[x][0]) + y.second;
    			f[y.first][1] = min(max(dp[x][1][0].first, f[x][0]), min(max(f[x][0], max(dp[x][1][1].first, dp[x][2][0].first)), max(dp[x][1][0].first, f[x][1])) + y.second);
    		} else {
    			f[y.first][0] = max(dp[x][0][0].first, f[x][0]) + y.second;
    			if(dp[x][1][0].second == y.first) {
    				f[y.first][1] = min(max(dp[x][0][0].first, f[x][0]), min(max(f[x][0], max(dp[x][0][1].first, dp[x][2][0].first)), max(dp[x][0][0].first, f[x][1])) + y.second);
    			} else {
    				f[y.first][1] = min(max(dp[x][0][0].first, f[x][0]), min(max(f[x][0], max(dp[x][0][1].first, dp[x][1][0].first)), max(dp[x][0][0].first, f[x][1])) + y.second);
    			}
    		}
    		dfs2(y.first, x);
    	}
    }
    int main() {
    	int T, n, u, v, w;
    //	freopen("in.txt", "r", stdin);
    //	freopen("out.txt", "w", stdout);
    	scanf("%d", &T);
    	while(T--) {
    		scanf("%d", &n);
    		for (int i = 1; i <= n; i++) {
    			G[i].clear();
    			memset(dp[i], 0, sizeof(dp[i]));
    			memset(f[i], 0, sizeof(f[i]));
    			d[i] = 0;
    		}
    		for (int i = 1; i < n; i++) {
    			scanf("%d%d%d", &u, &v, &w);
    			add(u, v, w);
    		}
    		dfs1(1, 0);
    		ans = max(dp[1][0][1].first, dp[1][1][0].first);
    		pos = 1;
    		dfs2(1, 0);
    		printf("%d %d\n", pos, ans);
    	}
    }

转载于:https://www.cnblogs.com/pkgunboat/p/11420039.html