換根DP

一般是給定一棵不定根樹(shù)，求以每個(gè)節(jié)點(diǎn)為根的一些信息。可以通過(guò)二次掃描：

• 第一次掃描，任選一點(diǎn)為根，在有根樹(shù)上，自底向上轉(zhuǎn)移
• 第二次掃描，從上一次掃描的根開(kāi)始，自頂向下計(jì)算

P3478 [POI2008] STA-Station

題意：

詢問(wèn)以哪個(gè)節(jié)點(diǎn)為根，所有節(jié)點(diǎn)的深度和最大。深度為到根節(jié)點(diǎn)的距離。

解析：

第一次掃描：以節(jié)點(diǎn)1為根(任意一個(gè)節(jié)點(diǎn)都可以)，求出深度和。

第二次掃描：設(shè)第一次掃描時(shí) $v$ 是 $u$ 的兒子。假設(shè)根節(jié)點(diǎn)由 $u$ 變?yōu)?$v$ ，$v$ 子樹(shù)內(nèi)所有節(jié)點(diǎn)的深度-1，不在 $v$ 子樹(shù)內(nèi)的所有節(jié)點(diǎn)深度+1。 $f_v=f_u?siz{e}_v+n?siz{e}_v$，$n$ 為所有節(jié)點(diǎn)數(shù)。

代碼：

#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

題意：

一棵樹(shù)，邊有邊權(quán)，點(diǎn)有點(diǎn)權(quán)。詢問(wèn)以哪個(gè)點(diǎn)為根時(shí)，$\sum _{i=1}^{n}dis(i,root)?a_i$。$a_i$ 為點(diǎn)權(quán)，$dis(i,root)$ 為節(jié)點(diǎn) $i$ 與根節(jié)點(diǎn)的距離。

解析：

第一次掃描：
以1節(jié)點(diǎn)為根，$f_u$ 表示 $u$ 子樹(shù)內(nèi)節(jié)點(diǎn)到 $u$ 距離點(diǎn)權(quán)的乘積的和。設(shè) $v$ 為 $u$ 的兒子，則 $f_u=\sum (f_v+siz{e}_v\times e(u,v))$，$e(u,v)$ 為 $(u,v)$ 邊的長(zhǎng)度。

第二次掃描：
設(shè)第一次掃描時(shí) $v$ 是 $u$ 的兒子。假設(shè)根節(jié)點(diǎn)由 $u$ 變?yōu)?$v$，$v$ 子樹(shù)內(nèi)所有節(jié)點(diǎn)到根節(jié)點(diǎn)的距離減小 $e(u,v)$，不在 $v$ 子樹(shù)內(nèi)的所有節(jié)點(diǎn)到根節(jié)點(diǎn)的距離增加 $e(u,v)$。 $f_v=f_u+(n?2\times siz{e}_v)\times e(u,v)$，$n$ 為所有節(jié)點(diǎn)數(shù)。

代碼：

#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;
}

積蓄程度

題意：

一棵樹(shù)，根節(jié)點(diǎn)可以流出無(wú)限水，葉子節(jié)點(diǎn)可以吸收無(wú)限水，每條邊有流量限制。詢問(wèn)以哪個(gè)點(diǎn)為根節(jié)點(diǎn)時(shí)，葉子節(jié)點(diǎn)吸收的水最多。

解析：

第一次掃描：

令 $f_u$ 為以1為根節(jié)點(diǎn)時(shí)，以 $u$ 為根的子樹(shù)中，吸收的水量。

設(shè) $v$ 為 $u$ 的兒子：
$$\{\begin{array}{ll}{f}_u+=min(f_v,w(u,v)),& de{g}_v=1\\ f_u+=w(u,v),& de{g}_v\ne 1\end{array}$$

第二次掃描：

令 $g_u$ 為以 $u$ 為根節(jié)點(diǎn)時(shí)，最大流量。

設(shè)第一次掃描時(shí) $v$ 是 $u$ 的兒子。假設(shè)根節(jié)點(diǎn)由 $u$ 變?yōu)?$v$

$g_v$ 包括兩部分:

• 一部分是第一次掃描的 $f_v$
• 一部分是流向 $u$ 進(jìn)而流向其他節(jié)點(diǎn)

對(duì) $u$ 而言，從 $u$ 到 $v$ 的流量為 $min(f_j,w(i,j))$，流向 $v$ 之外的流量為 $g_u?min(f_j,w(i,j))$。所以 $g_v$ 的第二部分為 $min(w(u,v),g_u?min(f_j,w(i,j)))$。也需要按照度是否為1討論一下：$$?\begin{array}{ll}{g}_v=f_v+w(u,v)& de{g}_u=1\\ g_v=f_v+min(g_u?w(u,v),w(u,v))& de{g}_u\ne 1,de{g}_v=1\\ g_v=f_v+min(g_u?min(f_v,w(u,v)),w(u,v)),& de{g}_u\ne 1,de{g}_v\ne 1\end{array}$$

代碼：

#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;elsef[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);elseg[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;
}