本文主要是介绍换根DP求树的重心/求最小距离和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
DP过程
const int N = 1e6+7; int Size[N] // Size[i]表示以i为根的子树的结点数 int dp[N] //dp[i]表示树中所有点到结点i的距离和dp[son]=dp[pos]+(Size[1]-Size[son])-Size[son]; //状态转移方程
预处理
-
预处理出所有Size
dfs
-
预处理出dp[1]
dfs
洛谷P1364 医院设置
[P1364 医院设置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1364)
分析
如果你非要用换根dp做的话。
那么这道题与模板的变化点就在于我们并不是要求树中点到某点的距离和最小
而是要求所有居民走的距离最短。
但换汤不换药，我们只要将每个Size[i] 初始化为i的点权就可以了
理由是：
当我们换根 i->j 时， j 的子树内所有的居民少走1个单位距离， j的子树外的所有居民多走1个单位距离。仍然与我们的换根dp实质相同
代码
cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<stack>
#include<list>
using namespace std;
const int N = 1e6 + 7;
vector<int> v[N];
int Size[N];
int Val[N];
long long dp[N];
void get_size(int pos, int depth, int fa) {Size[pos] = Val[pos]; // 节点pos的初始子树大小为节点权值for (int i = 0; i < v[pos].size(); i++) { // 遍历节点pos的所有子节点int son = v[pos][i]; // 获取子节点if (son != fa) { // 如果子节点不是父节点，则递归计算子节点的子树大小get_size(son, depth + 1, pos);Size[pos] += Size[son]; // 累加子节点的子树大小到父节点}}dp[1] += depth * Val[pos]; // 计算动态规划值，累加节点深度乘以权值
}
long long ans = 2147483647; // 初始化最小值为int型最大值
// 动态规划
void DP(int pos, int fa) {for (int i = 0; i < v[pos].size(); i++) { // 遍历节点pos的所有子节点int son = v[pos][i]; // 获取子节点if (son != fa) { // 如果子节点不是父节点，则进行动态规划dp[son] = dp[pos] + Size[1] - 2 * Size[son]; // 更新子节点的动态规划值DP(son, pos); // 递归调用动态规划}}ans = min(ans, dp[pos]); // 更新最小值
}
int main() {int n; // 节点数量cin >> n; // 输入节点数量ans *= ans; // 将最小值平方，初始化为一个足够大的数
for (int i = 1; i <= n; i++) { // 遍历每个节点int val, begin, end; // 节点权值、子节点1、子节点2cin >> val >> begin >> end; // 输入节点权值、子节点1、子节点2Val[i] = val; // 存储节点权值
if (begin) { // 如果子节点1存在v[i].push_back(begin); // 将子节点1添加到节点i的邻接表中v[begin].push_back(i); // 将节点i添加到子节点1的邻接表中}
if (end) { // 如果子节点2存在v[i].push_back(end); // 将子节点2添加到节点i的邻接表中v[end].push_back(i); // 将节点i添加到子节点2的邻接表中}}
get_size(1, 0, -1); // 计算每个节点的子树大小DP(1, 1); // 进行动态规划cout << ans; // 输出最小值
}
洛谷P1395会议
比上一题还简单，没意思的模板题。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<stack>
#include<list>
using namespace std;
const int N = 1e5 + 7;
vector<int> v[N];
int Size[N]; int d[N];
int use[N];
int n;
void get_size(int now,int fa) {
Size[now] = 1;
for (int i = 0; i < v[now].size(); i++) {if (v[now][i] != fa) {get_size(v[now][i], now);Size[now] += Size[v[now][i]];}}}
// d[now] = d[fa]+ Size[1]-2*Size[now] ;
int get_d1(int now,int fa,int depth) {int ans = 0;
for (int i = 0; i < v[now].size(); i++) {if (v[now][i] != fa) {ans+=get_d1(v[now][i], now,depth+1)+depth;}}return ans;
}
void get_alld(int now, int fa) {use[now] = 1;for (int i = 0; i < v[now].size(); i++) {int son = v[now][i];//and use[son] == 0if (son != fa and use[son] == 0) {d[son] = d[now] + Size[1] - 2 * Size[son];get_alld(son, fa);}}
}
// 6+4-6=4
int main() {cin >> n;if (n == 0) {cout << 0<<' '<<0;return 0;}
for (int i = 1; i <= n - 1; i++) {
int a, b;cin >> a >> b;
v[a].push_back(b);v[b].push_back(a);
}
get_size(1, 0);
d[1]=get_d1(1, 0,1);get_alld(1, 0);
int minn = 0x7fffffff;int pos = 0;
for (int i = 1; i <= n; i++) {if (d[i] < minn) {pos = i;minn = d[i];}}cout << pos << ' ' << minn;
}
这篇关于换根DP求树的重心/求最小距离和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
