算法笔记-换根DP
换根DP
一般是给定一棵不定根树，求以每个节点为根的一些信息。可以通过二次扫描：
- 第一次扫描，任选一点为根，在有根树上，自底向上转移
- 第二次扫描，从上一次扫描的根开始，自顶向下计算
P3478 [POI2008] STA-Station
题意：
询问以哪个节点为根，所有节点的深度和最大。深度为到根节点的距离。
解析：
第一次扫描：以节点1为根(任意一个节点都可以)，求出深度和。
第二次扫描：设第一次扫描时 v v v 是 u u u 的儿子。假设根节点由 u u u 变为 v v v ， v v v 子树内所有节点的深度-1，不在 v v v 子树内的所有节点深度+1。 f v = f u − s i z e v + n − s i z e v f_v= f_u-size_v+n-size_v fv=fu−sizev+n−sizev， n n n 为所有节点数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
struct edge{
int to, nxt;
}e[maxn << 1];
int head[maxn], siz[maxn], tot, dep[maxn];
void add(int a, int b){
e[++tot].nxt = head[a];
e[tot].to = b;
head[a] = tot;
}
int n, m;
ll f[maxn];
void dfs(int u, int fa){
siz[u] = 1;
dep[u] = dep[fa] + 1;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa)
continue;
dfs(v, u);
siz[u] += siz[v];
}
}
void dfs2(int u, int fa){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa)
continue;
f[v] = f[u] + n - siz[v] * 2;
dfs2(v, u);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
add(u, v); add(v, u);
}
dfs(1, 0);
for(int i = 1; i <= n; i++)
f[1] += dep[i];
dfs2(1, 0);
ll maxx = -1, res;
for(int i = 1; i <= n; i++){
if(maxx < f[i]){
res = i;
maxx = f[i];
}
}
cout << res << endl;
return 0;
}
P2986 [USACO10MAR] Great Cow Gathering G
题意：
一棵树，边有边权，点有点权。询问以哪个点为根时， ∑ i = 1 n d i s ( i , r o o t ) ⋅ a i \sum\limits_{i=1}\limits^ndis(i, root) \cdot a_i i=1∑ndis(i,root)⋅ai。 a i a_i ai 为点权， d i s ( i , r o o t ) dis(i,root) dis(i,root) 为节点 i i i 与根节点的距离。
解析：
第一次扫描：
以1节点为根，
f
u
f_u
fu 表示
u
u
u 子树内节点到
u
u
u 距离点权的乘积的和。设
v
v
v 为
u
u
u 的儿子，则
f
u
=
∑
(
f
v
+
s
i
z
e
v
×
e
(
u
,
v
)
)
f_u =\sum(f_v+size_v\times e(u,v))
fu=∑(fv+sizev×e(u,v))，
e
(
u
,
v
)
e(u,v)
e(u,v) 为
(
u
,
v
)
(u,v)
(u,v) 边的长度。
第二次扫描：
设第一次扫描时
v
v
v 是
u
u
u 的儿子。假设根节点由
u
u
u 变为
v
v
v，
v
v
v 子树内所有节点到根节点的距离减小
e
(
u
,
v
)
e(u,v)
e(u,v)，不在
v
v
v 子树内的所有节点到根节点的距离增加
e
(
u
,
v
)
e(u,v)
e(u,v)。
f
v
=
f
u
+
(
n
−
2
×
s
i
z
e
v
)
×
e
(
u
,
v
)
f_v= f_u+(n-2\times size_v)\times e(u,v)
fv=fu+(n−2×sizev)×e(u,v)，
n
n
n 为所有节点数。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e6+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int, int> pii;
#define int ll
struct edge{
int to, nxt, w;
}e[maxn << 1];
int head[maxn], siz[maxn], tot;
void add(int a, int b, int c){
e[++tot].nxt = head[a];
e[tot].to = b;
e[tot].w = c;
head[a] = tot;
}
int n, m;
ll f[maxn], a[maxn], sum;
void dfs(int u, int fa){
siz[u] = a[u];
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa)
continue;
dfs(v, u);
siz[u] += siz[v];
f[u] += f[v] + siz[v] * e[i].w;
}
}
void dfs2(int u, int fa){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa)
continue;
f[v] = f[u] - siz[v] * e[i].w + (sum - siz[v]) * e[i].w;
dfs2(v, u);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
}
for(int i = 1; i < n; i++){
int u, v, w;
cin >> u >> v >> w;
add(u, v, w); add(v, u, w);
}
dfs(1, 0);
dfs2(1, 0);
ll res = INF;
for(int i = 1; i <= n; i++)
res = min(res, f[i]);
cout << res << endl;
return 0;
}
积蓄程度
题意：
一棵树，根节点可以流出无限水，叶子节点可以吸收无限水，每条边有流量限制。询问以哪个点为根节点时，叶子节点吸收的水最多。
解析：
第一次扫描：
令 f u f_u fu 为以1为根节点时，以 u u u 为根的子树中，吸收的水量。
设
v
v
v 为
u
u
u 的儿子：
{
f
u
+
=
m
i
n
(
f
v
,
w
(
u
,
v
)
)
,
d
e
g
v
=
1
f
u
+
=
w
(
u
,
v
)
,
d
e
g
v
≠
1
\begin{cases} f_u += min(f_v, w(u, v)), & deg_v = 1\\ f_u += w(u, v), & deg_v \neq 1 \end{cases}
{fu+=min(fv,w(u,v)),fu+=w(u,v),degv=1degv=1
第二次扫描：
令 g u g_u gu 为以 u u u 为根节点时，最大流量。
设第一次扫描时 v v v 是 u u u 的儿子。假设根节点由 u u u 变为 v v v
g v g_v gv 包括两部分:
- 一部分是第一次扫描的 f v f_v fv
- 一部分是流向 u u u 进而流向其他节点
对 u u u 而言，从 u u u 到 v v v 的流量为 m i n ( f j , w ( i , j ) ) min(f_j, w(i,j)) min(fj,w(i,j))，流向 v v v 之外的流量为 g u − m i n ( f j , w ( i , j ) ) g_u - min(f_j, w(i,j)) gu−min(fj,w(i,j))。所以 g v g_v gv 的第二部分为 m i n ( w ( u , v ) , g u − m i n ( f j , w ( i , j ) ) ) min(w(u,v), g_u - min(f_j, w(i,j))) min(w(u,v),gu−min(fj,w(i,j)))。也需要按照度是否为1讨论一下： { g v = f v + w ( u , v ) d e g u = 1 g v = f v + m i n ( g u − w ( u , v ) , w ( u , v ) ) d e g u ≠ 1 , d e g v = 1 g v = f v + m i n ( g u − m i n ( f v , w ( u , v ) ) , w ( u , v ) ) , d e g u ≠ 1 , d e g v ≠ 1 \begin{cases} g_v = f_v+ w(u, v) & deg_u = 1\\ g_v = f_v + min(g_u-w(u,v), w(u, v)) °_u \neq 1 ,deg_v = 1\\ g_v = f_v + min(g_u-min(f_v, w(u,v)), w(u,v)),& deg_u \neq 1 ,deg_v \neq 1 \end{cases} ⎩ ⎨ ⎧gv=fv+w(u,v)gv=fv+min(gu−w(u,v),w(u,v))gv=fv+min(gu−min(fv,w(u,v)),w(u,v)),degu=1degu=1,degv=1degu=1,degv=1
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
#define int ll
struct edge{
int to, nxt, w;
}e[maxn << 1];
int head[maxn], siz[maxn], tot;
void add(int a, int b, int c){
e[++tot].nxt = head[a];
e[tot].to = b;
e[tot].w = c;
head[a] = tot;
}
int n, m;
ll f[maxn], g[maxn], deg[maxn];
void dfs(int u, int fa){
f[u] = 0;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa)
continue;
dfs(v, u);
if(deg[v] == 1)
f[u] += e[i].w;
else
f[u] += min(e[i].w, f[v]);
}
}
void dfs2(int u, int fa){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa)
continue;
if(deg[u] == 1)
g[v] = f[v] + e[i].w;
else if(deg[v] == 1)
g[v] = f[v] + min(g[u]-e[i].w, e[i].w);
else
g[v] = f[v] + min(g[u]-min(f[v], e[i].w), e[i].w);
dfs2(v, u);
}
}
void solve(){
cin >> n;
memset(deg, 0, sizeof(deg));
tot = 0;
memset(head, 0, sizeof(head));
for(int i = 1; i < n; i++){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
deg[a]++; deg[b]++;
}
dfs(1, 0);
g[1] = f[1];
dfs2(1, 0);
ll res = 0;
for(int i = 1; i <= n; i++)
res = max(res, g[i]);
cout << res << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin >> T;
while(T--)
solve();
return 0;
}