0x54 树形DP

285. 没有上司的舞会

题意：

上司关系构成一棵树，一个人不能和直系上司同时出现在舞会，每个人有点权，询问能同时出现在舞会上的最大权值和。（最大权独立集）

解析：

令 fu,0/1f_{u,0/1}fu,0/1​ 为以 $u$ 为根的树满足条件的最大权值和。

如果选了上司，所有儿子都不能选；如果没选上司，儿子可选可不选
{fu,0=∑max⁡(fv,0,fv,1)fu,1=∑fv,0\\begin{cases} f_{u, 0} = \\sum\\max(f_{v, 0}, f_{v, 1}) \\\\ f_{u, 1}= \\sum f_{v, 0} \\end{cases} {fu,0​=∑max(fv,0​,fv,1​)fu,1​=∑fv,0​​

代码：

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int read() {int x = 0, f = 1;char c = getchar();while(c<'0' || c>'9'){if(c == '-') f = -1;c = getchar();}while(c>='0' && c<='9') {x = x*10 + c-'0';c = getchar();}		return x * f;
}
void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x/10);putchar(x%10 + '0');
}int n, a[maxn];
int f[maxn][2];
struct edge{int to, nxt;
}e[maxm << 1];
int head[maxn], fa[maxn], tot, rt;
void add(int a, int b){e[++tot].nxt = head[a];e[tot].to = b;head[a] = tot;
}
void dfs(int u, int fa){f[u][1] = a[u];for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;if(v == fa)continue;dfs(v, u);f[u][0] += max(f[v][0], f[v][1]);f[u][1] += f[v][0];}
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i < n; i++){int u, v;cin >> u >> v;add(v, u);fa[u] = v;}for(int i = 1; i <= n; i++)if(fa[i] == 0)rt = i;dfs(rt, 0);cout << max(f[rt][0], f[rt][1]) << endl;return 0;
}

选课

题意：

$n$ 门课，每门课有一定的学分，需要选 $m$ 门。有些课有先修课，选了先修课才能选当前课。询问最多学分。

解析：

令 fu,kf_{u, k}fu,k​ 为以 $u$ 为根的子树中，选 $k$ 门课的最大学分。

对每个节点 $u$ 来说，分组背包，从每个儿子中选一定的课。

代码：

#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef double db;
#define fi first
#define se second
const int maxn = 3e2+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;int read() {int x = 0, f = 1;char c = getchar();while(c<'0' || c>'9'){if(c == '-') f = -1;c = getchar();}while(c>='0' && c<='9') {x = x*10 + c-'0';c = getchar();}		return x * f;
}
void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x/10);putchar(x%10 + '0');
}
struct edge{int to, nxt;
}e[maxm << 1];
int head[maxn], fa[maxn], tot, rt;
void add(int a, int b){e[++tot].nxt = head[a];e[tot].to = b;head[a] = tot;
}
int n, m, a[maxn];
int f[maxn][maxm];void dfs(int u){for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;dfs(v);}for(int i = head[u]; i; i = e[i].nxt){int v = e[i].to;for(int j = m; j > 0; j--){for(int k = 0; k < j; k++)f[u][j] = max(f[u][j], f[u][j-k]+f[v][k]);}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;m++;//memset(f, -INF, sizeof(f));for(int i = 1; i <= n; i++){cin >> fa[i] >> f[i][1];add(fa[i], i);}	dfs(0);cout << f[0][m];return 0;
}

积蓄程度

题意：

一棵树，根节点可以流出无限水，叶子节点可以吸收无限水，每条边有流量限制。询问以哪个点为根节点时，叶子节点吸收的水最多。

解析：

第一次扫描：

令 fuf_ufu​ 为以1为根节点时，以 $u$ 为根的子树中，吸收的水量。

设 $v$ 为 $u$ 的儿子：
{fu+=min(fv,w(u,v)),degv=1fu+=w(u,v),degv≠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​

第二次扫描：

令 gug_ugu​ 为以 $u$ 为根节点时，最大流量。

设第一次扫描时 $v$ 是 $u$ 的儿子。假设根节点由 $u$ 变为 $v$

gvg_vgv​ 包括两部分:

• 一部分是第一次扫描的 fvf_vfv​
• 一部分是流向 $u$ 进而流向其他节点

对 $u$ 而言，从 $u$ 到 $v$ 的流量为 min(fj,w(i,j))min(f_j, w(i,j))min(fj​,w(i,j))，流向 $v$ 之外的流量为 gu−min(fj,w(i,j))g_u - min(f_j, w(i,j))gu​−min(fj​,w(i,j))。所以 gvg_vgv​ 的第二部分为 min(w(u,v),gu−min(fj,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讨论一下：{gv=fv+w(u,v)degu=1gv=fv+min(gu−w(u,v),w(u,v))degu≠1,degv=1gv=fv+min(gu−min(fv,w(u,v)),w(u,v)),degu≠1,degv≠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)) &deg_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;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;
}