百度网站怎么做信息,优化方案化学,私人可以做org后缀网站吗,免费com域名注册永久树形 d p dp dp
例1 - 基础
链接#xff1a;树上子链
练手
分析
其实一看题就很显然的树形 d p dp dp子链在这里分为两种情况#xff0c;如图黑链和红链
思路 d p [ i ] dp[i] dp[i] 表示以 i i i 开头的红链的最大权值易得#xff1a; d p [ i ] m a x ( d p [ i…树形 d p dp dp
例1 - 基础
链接树上子链
练手
分析
其实一看题就很显然的树形 d p dp dp子链在这里分为两种情况如图黑链和红链
思路 d p [ i ] dp[i] dp[i] 表示以 i i i 开头的红链的最大权值易得 d p [ i ] m a x ( d p [ i ] , a [ u ] d p [ v ] ) dp[i] max(dp[i], a[u] dp[v]) dp[i]max(dp[i],a[u]dp[v])黑链的更新你可以另设一个 d p dp dp 也可以直接更新答案 a n s m a x ( a n s , d p [ u ] d p [ v ] ) ans max(ans, dp[u] dp[v]) ansmax(ans,dp[u]dp[v])黑链存在的话一定是最长两条红链的和应该说是两条子红链加父亲节点权值 你可以想想这样为什么行
#include bits/stdc.husing ll long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin n;std::vectorll a(n 1);for (int i 1; i n; i) {std::cin a[i];}std::vectorstd::pairint ,int e((n 1) 1);std::vectorint head(n 1);int cnt 0;auto add [](int u, int v) {e[cnt] {v, head[u]}, head[u] cnt;};for (int i 1; i n; i) {int u, v;std::cin u v;add(u, v);add(v, u);}ll ans -1e18;std::vectorll dp(n 1);std::functionvoid(int, int) dfs [](int u, int f) {dp[u] a[u];for (int i head[u]; i; i e[i].second) {int v e[i].first;if (v xor f) {dfs(v, u);ans std::max(ans, dp[u] dp[v]);dp[u] std::max(dp[u], a[u] dp[v]);}}ans std::max(ans, dp[u]);};dfs(1, 0);std::cout ans;return 0;
}例2 - 进阶
链接二叉苹果树
练手
分析
树上背包
思路
设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示以 i i i 节点保留 j j j 条树枝最多苹果数量。易得 ∑ j 2 m ∑ k 1 , k j s z [ v ] d p [ u ] [ j ] m a x ( d p [ u ] [ j ] , d p [ u ] [ j − k ] d p [ v ] [ k ] \sum\limits_{j2}^m \sum\limits_{k1,kj}^{sz[v]}dp[u][j]max(dp[u][j],dp[u][j-k]dp[v][k] j2∑mk1,kj∑sz[v]dp[u][j]max(dp[u][j],dp[u][j−k]dp[v][k] 。注意这里的二维其实相当于普通背包的一维所以 j j j 的枚举应该倒序。
#includebits/stdc.husing ll long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, q;std::cin n q;q;std::vectorstd::tupleint, int, int e((n 1) 1);std::vectorint head(n 1);int cnt 0;auto add [](int u, int v, int w) {e[cnt] {v, w, head[u]}, head[u] cnt;};for (int i 1; i n; i) {int u, v, w;std::cin u v w;add(u, v, w);add(v, u, w);}std::vectorstd::vectorint dp(n 1, std::vectorint(q 1));std::vectorint sz(n 1);std::functionvoid(int, int, int) dfs [](int u, int f, int m) {sz[u] 1;for (int i head[u]; i;) {auto [v, w, nxt] e[i];if (f xor v) {dp[v][1] w;dfs(v, u, m);sz[u] sz[v];for (int j m; j 1; --j) {for (int k 1; k sz[v] and k j; k) {dp[u][j] std::max(dp[u][j], dp[u][j - k] dp[v][k]);}}}i nxt;}};dfs(1, 0, q);std::cout dp[1][q];return 0;
}例3 - 困难
链接树上染色
练手这个更难
分析
可以考虑上题一样就背包思想枚举。
思路
设 d p [ u ] [ j ] dp[u][j] dp[u][j] 为 u u u 节点 染 j j j 个为黑色最大效益。易得 ∑ j 0 m i n ( k , s z [ u ] ) ∑ l 0 m i n ( s z [ v ] , l ) d p [ u ] [ j ] m a x ( d p [ u ] [ j ] , d p [ u ] [ j − l ] d p [ v ] [ l ] v a l \sum\limits_{j0}^{min(k,sz[u])} \sum\limits_{l0}^{min(sz[v],l)}dp[u][j] max(dp[u][j], dp[u][j-l]dp[v][l]val j0∑min(k,sz[u])l0∑min(sz[v],l)dp[u][j]max(dp[u][j],dp[u][j−l]dp[v][l]val 。 v a l val val 即是很常见的计算贡献的思想。考虑一条边把树分成两部分树 A A A 树 B B B 树 B B B 选择 l l l 个点染黑色那么另外 k − l k - l k−l 个黑色节点即在树 A A A那么这条边就会被计算 l × ( k − l ) l \times (k-l) l×(k−l) 次贡献即为 l × ( k − l ) × w l\times(k-l)\times w l×(k−l)×w 。树 B B B 的另外 s z [ B ] − l sz[B]-l sz[B]−l 个节点即为白色那么另外 n − k − ( s z [ B ] − l ) n-k-(sz[B]-l) n−k−(sz[B]−l) 个白色节点即在树 A A A 所以该边白色贡献为 ( s z [ B ] − l ) × ( n − k − ( s z [ B ] − l ) ) ∗ w (sz[B] - l) \times (n - k - (sz[B] - l)) * w (sz[B]−l)×(n−k−(sz[B]−l))∗w 。同样倒序枚举 j j j 。
#include bits/stdc.husing ll long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, k;std::cin n k;std::vectorstd::tupleint, ll, int e((n 1) 1);std::vectorint head(n 1);int cnt 0;auto add [](int u, int v, ll w) {e[cnt] {v, w, head[u]}, head[u] cnt;};for (int i 1; i n; i) {int u, v;ll w;std::cin u v w;add(u, v, w);add(v, u, w);}std::vectorstd::vectorll dp(n 1, std::vectorll(k 1, -1));std::vectorint sz(n 1);std::functionvoid(int, int) dfs [](int u, int f) {sz[u] 1;dp[u][0] dp[u][1] 0;for (int i head[u]; i;) {auto [v, w, nxt] e[i];if (v xor f) {dfs(v, u);sz[u] sz[v];for (int j std::min(k, sz[u]); j 0; --j) {for (int l 0; l std::min(sz[v], k); l) {if (dp[u][j - l] not_eq -1 and j l) {ll val 1ll * l * (k - l) * w 1ll * (sz[v] - l) * (n - k - (sz[v] - l)) * w;dp[u][j] std::max(dp[u][j], dp[u][j - l] dp[v][l] val);}}}}i nxt;}};dfs(1, 0);std::cout dp[1][k];return 0;
}
