1 问题
给定一棵无向无权树,对每个节点
其中
如果从每个节点出发,各遍历一次全树,时间复杂度为
2 固定一个根
先以
| 信息 | 含义 |
|---|---|
| 固定根下, |
|
孩子先于父亲计算,有:
从
根的子树就是全树,因此
3 沿边换根
考虑固定根下的一条父子边
子树中的 个点,距离都减少 。 - 其余
个点,距离都增加 。
所以:
这里的
4 计算顺序
两遍计算分别满足不同的依赖关系:
- 孩子先于父亲:求
、 ,得到 。 - 父亲先于孩子:利用
和 ,求 。
可以使用两次 DFS,也可以先记录父亲先于孩子的遍历顺序。倒序处理完成第一遍,正序处理完成第二遍。后者不依赖递归栈,适合很长的链。
5 手算示例
图中的树有边
| 节点 |
换根计算 | |||
|---|---|---|---|---|
| 1 | 5 | 6 | 初始根 | 6 |
| 2 | 1 | 0 | 9 | |
| 3 | 3 | 2 | 5 | |
| 4 | 1 | 0 | 8 | |
| 5 | 1 | 0 | 8 |
从
6 正确性
第一遍的子树划分互不重叠,公式将每个孩子子树的内部距离整体增加一条边,故正确求出
对任意父子边,边的两侧恰好划分全树所有节点,每个节点的距离变化都已计入
第二遍中父亲先于孩子,每个节点都能沿从初始根到它的唯一路径得到正确答案。
7 代码实现
下面的完整程序读入
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;
vector<int> g[maxn];
int fa[maxn], order[maxn], sz[maxn];
ll down[maxn], ans[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
order[1] = 1;
int total = 1;
for (int i = 1; i <= total; ++i) {
int u = order[i];
for (int v : g[u]) {
if (v == fa[u]) continue;
fa[v] = u;
order[++total] = v;
}
}
// 第一遍:孩子先于父亲,统计子树大小与子树内部距离和。
for (int i = total; i >= 1; --i) {
int u = order[i];
sz[u] = 1;
for (int v : g[u]) {
if (v == fa[u]) continue;
sz[u] += sz[v];
down[u] += down[v] + sz[v]; // 孩子子树中每个点都要多走一条边
}
}
ans[1] = down[1];
// 第二遍:父亲先于孩子,沿父子边推导全树答案。
for (int i = 2; i <= total; ++i) {
int v = order[i], u = fa[v];
ans[v] = ans[u] + n - 2LL * sz[v];
}
for (int u = 1; u <= n; ++u) {
cout << ans[u] << (u == n ? '\n' : ' ');
}
return 0;
}
时间复杂度为 int,所以距离和使用 long long。
8 点权与边权
若节点
记全树点权和为
第一遍相应改为:
点权控制一份距离贡献的倍数,边权控制一次移动的长度,两者作用不同。将点权和边长都设为
带权完整代码
下面采用通用输入格式:第一行 u v 长度。输出每个节点的加权距离和。它与具体例题的输入格式不同,使用时需要对应调整。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;
struct Edge {
int to;
ll w;
};
vector<Edge> g[maxn];
int fa[maxn], order[maxn];
ll weight[maxn], sub[maxn], down[maxn], ans[maxn], parent_len[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int u = 1; u <= n; ++u) cin >> weight[u];
for (int i = 1; i < n; ++i) {
int u, v;
ll len;
cin >> u >> v >> len;
g[u].push_back({v, len});
g[v].push_back({u, len});
}
order[1] = 1;
int total = 1;
for (int i = 1; i <= total; ++i) {
int u = order[i];
for (auto [v, len] : g[u]) {
if (v == fa[u]) continue;
fa[v] = u;
parent_len[v] = len;
order[++total] = v;
}
}
for (int i = total; i >= 1; --i) {
int u = order[i];
sub[u] = weight[u];
for (auto [v, len] : g[u]) {
if (v == fa[u]) continue;
sub[u] += sub[v];
down[u] += down[v] + sub[v] * len;
}
}
ans[1] = down[1];
ll total_weight = sub[1];
for (int i = 2; i <= total; ++i) {
int v = order[i], u = fa[v];
ans[v] = ans[u] + (total_weight - 2 * sub[v]) * parent_len[v];
}
for (int u = 1; u <= n; ++u) {
cout << ans[u] << (u == n ? '\n' : ' ');
}
return 0;
}
模板使用 long long 保存点权和、乘积与答案。需要按数据范围检查这些量,例如
9 应用
- luogu P1364: 医院设置:点权是居民人数,边长为
,求所有 的最小值;输入为每个节点的人数与两个孩子编号。 - luogu P3478: [POI 2008] STA-Station:所有点权、边长均为
,求距离和最大的节点,输出编号。原题 ,需要相应扩大数组。
无权树上,使距离和最小的节点与 树的重心 有关;换根DP则直接求出了每个候选节点的完整目标值。
10 相关题解
暂无相关题解