【二次扫描换根法】JZOJ_5776 小x游世界树

本文主要是介绍【二次扫描换根法】JZOJ_5776 小x游世界树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

一棵有$N$个节点的树，上面每个点都有一个魔法阵，走到了这个点上会被魔法阵传送回根节点，每个魔法阵只能用一次，且每个节点上有一个加速平台，可以使以这个点为起点的边需要的体力值减小。求以哪个节点为根可以使得走到每一个点的体力值总和最小。

思路

我们可以发现，一条边需要走$z{s}_y$次，其中$y$为边的终点，$z{s}_i$代表节点$i$的子树节点总和(包括$i$)，我们可以先求出根节点为$1$时的最小体力值以及每个点的子树个数，然后进行换根操作。
我们设$f_i$为$i$为根节点时的最小体力值，可以得出转移方程：
$f_y=f_x-z{s}_y\ast (w-q_x)+(N-z{s}_y)\ast (w-q_y)$，其中$w$代表$w(x,y)$，$q_i$代表这个点的加速平台可以减少的体力值
自行画图理解(逃

代码

#include<cstdio>struct node {int to, w, next;
}e[1400001];
int head[700001], zs[700001], q[700001];
long long f[700001];
int N, tot = 1, ans = 1;void dfs_(int fa, int p) {//第一次扫描zs[p] = 1;for (int i = head[p]; i; i = e[i].next) {if (e[i].to == fa) continue; dfs_(p, e[i].to);zs[p] += zs[e[i].to];f[1] += (e[i].w - q[p]) * zs[e[i].to];}
}void dfs__(int fa, int p) {//换根if (f[p] < f[ans] || (f[p] == f[ans] && p < ans)) ans = p;for (int i = head[p]; i; i = e[i].next) {if (e[i].to == fa) continue;f[e[i].to] = f[p] - zs[e[i].to] * (e[i].w - q[p]) + (N - zs[e[i].to]) * (e[i].w - q[e[i].to]);dfs__(p, e[i].to);}
}int main() {scanf("%d", &N);for (int i = 1; i <= N; i++) scanf("%d", q + i);int x, y, z; for (int i = 1; i < N; i++) {scanf("%d %d %d", &x, &y, &z);e[++tot] = (node){y, z, head[x]};head[x] = tot;e[++tot] = (node){x, z, head[y]};head[y] = tot;}dfs_(0, 1);dfs__(0, 1);printf("%d\n%lld", ans, f[ans]);
}

这篇关于【二次扫描换根法】JZOJ_5776 小x游世界树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---