换根树形动态规划
考虑以1为根的情况,size[i]表示以i为根的子树中有多少个点,f[i]表示考虑以i为根的子树,i到子树其他所有点的距离的和;
假设j是i的儿子,以j为根的子树对f[i]的贡献为f[j]+size[j]
\[f[i] = \sum_{j\in son(i)}(f[j]+size[j])= \sum_{j\in son(i)}(f[j]) + size[i] -1 \]当根从1变到他的儿子i的时候呢？
这时除了1为根时考虑的子树(贡献为f[i]),多了一个以1为根的子树,后面贡献怎么求？
用v[i]表示一个点的父亲作为它的子树时的贡献,v[i] = 0;
根从1号点变成其儿子结点:
\[v[i] = v[1] + f[1] - f[i] - size[i] + n - size[i]; \]\(v[1]\)
这里添加是为了更好的理解普通情况, 根从某个点变为其子节点时子节点继承v[i]
\(f[1] - f[i] - size[i]\)
此时1号点变为子节点减去现在作为根的节点对1号点的贡献
\(n-size[i]\)
当i号点作为根节点时, 此时原来以1号点为根的结点(1号点及原来以i号点为根的子树外的所有结点)都要让距离加一才能到i号点
根从x变为儿子y:
除了1为根时考虑的子树(贡献为f[y]), 多了一个以x为根的子树, 后面这个贡献:
\(v[y] = v[x] + f[x] - f[y] - size[y] + n - size[y];\)
此时答案就变成了子树内的距离f[i]加上v[i], \(f[i]+v[i]\)
时间复杂度\(O(n)\)
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5 + 10;
int n, l, siz[N];
vector<int> g[N];
LL f[N], v[N];
bool b[N];
void up(int i) {
siz[i] = 1;
b[i] = true;
for (int j : g[i]) {
if (!b[j]) {
up(j);
siz[i] += siz[j];
f[i] += f[j];
}
}
f[i] += siz[i] - 1;
}
void down(int i) {
b[i] = true;
for (int j : g[i]) {
if (!b[j]) {
v[j] = v[i] + f[i] - f[j] - siz[j] + n - siz[j];
down(j);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
memset(b, false, sizeof(b));
up(1);
memset(b, false, sizeof(b));
down(1);
for (int i = 1; i <= n; i++) {
printf("%lld\n", f[i] + v[i]);
}
return 0;
}
考虑以1为根的有根树的情况, f[i] 表示考虑以i为根的子树, 最多可以承接多少上面下来的流量;
假设j是i的儿子, 以j为根的子树对f[i]的贡献为\(min(c[j], f[j])\),其中c[j]表示j到i的边的流量限制;
\[f[i] = \sum_{j\in son(i)}min(c[j], f[j]) \]当根从1变为儿子i时:
除了1为根时考虑的子树(贡献为f[i]), 多了一个以1为根的子树, 后面贡献怎么求?
v[i] 表示一个点的父亲作为它的子树时的贡献, v[1] = 0;
\[v[i] = min(v[1] + f[1] - min(c[i], f[i]), c[i]) \]当根从x变为儿子y时:
除了以1为根时考虑的子树(贡献为f[y]), 多了一个以x为根的子树
对于y, 答案\(v[y] + f[y]\)
时间复杂度\(O(n)\)
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5 + 10;
int n, l;
vector<PII> g[N];
LL f[N], v[N];
bool b[N];
void up(int i) {
b[i] = true;
bool ok = true;
for (auto j : g[i]) {
if (!b[j.x]) {
up(j.x);
f[i] += min(1LL * j.y, f[j.x]);
ok = false;
}
}
if (ok) f[i] = 1 << 30;
}
void down(int i) {
b[i] = true;
for (auto j : g[i]) {
if (!b[j.x]) {
if (v[i] + f[i] - min(1LL * j.y, f[j.x]))
v[j.x] = min(v[i] + f[i] - min(1LL * j.y, f[j.x]), 1LL * j.y);
else
v[j.x] = j.y;
down(j.x);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int x, y, z;
scanf("%d%d%d,", &x, &y, &z);
g[x].push_back({y, z});
g[y].push_back({x, z});
}
memset(b, false, sizeof(b));
up(1);
memset(b, false, sizeof(b));
down(1);
for (int i = 1; i <= n; i++) {
// printf("%lld\n", f[i] + v[i]);
if (f[i] != 1 << 30)
printf("%lld\n", f[i] + v[i]);
else
printf("%lld\n", v[i]);
}
return 0;
}
考虑以1为根的有根树, f[i]数组记录考虑以i为跟的子树, 从i的不同子树连上来的到i的最长的两条路径;
假设j是i的儿子, 以j为根的子树连上来的路径是连到j的最长路径加i
维护到i的最长的两条路径是: 到1的最长的两条路径的长度的和
根从1变为儿子i时:
此时除了1为根时考虑的子树(f[i]维护了到i的最长的两条路径), 多了一个以1为根的子树
v[i]表示一个点的父亲作为它的子树时从里面连上来的到i的最长路径
v[i]的维护:
直觉上应该将连到1号点的最长路径加1接上j的最长路径, 但是如果1号点的最长路径就是j提供的此时就同一条路加两次了, 要分辨一下
根从x变为儿子y时:
v[y]的维护:
对于y, 以它为根时的答案等于f[y]维护的两条路劲和v[y]维护的路径中较长的两条
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5 + 10;
vector<int> g[N];
int n, f[N][2][2], v[N];
bool b[N];
void up(int i) {
b[i] = true;
for (int j : g[i]) {
if (!b[j]) {
up(j);
if (f[j][0][0] + 1 > f[i][0][0])
f[i][1][0] = f[i][0][0], f[i][1][1] = f[i][0][1],
f[i][0][0] = f[j][0][0] + 1, f[i][0][1] = j;
else if (f[j][0][0] + 1 > f[i][1][0])
f[i][1][0] = f[j][0][0] + 1, f[i][1][1] = j;
}
}
}
void down(int i) {
b[i] = true;
for (int j : g[i]) {
if (!b[i]) {
if (f[i][0][1] == j)
if (v[i] > f[i][1][0])
v[j] = v[i] + 1;
else
v[j] = f[i][1][0] + 1;
else
v[j] = max(f[i][0][0], v[i]) + 1;
down(j);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
memset(b, false, sizeof(b));
up(1);
memset(b, false, sizeof(b));
down(1);
for (int i = 1; i <= n; i++)
printf("%d\n", f[i][0][0] + f[i][1][0] + v[i] -
min(min(f[i][0][0], f[i][1][0]), v[i]));
return 0;
}