给定一棵树 每个节点都为黑色 将某些节点变为白色 使每条边的两端至少有一个白色 问最少需改变的点
\(f_{u, 0} = \sum f_{v, 1}\)
\(f_{u, 1} = \sum \max \{f_{v, 0}, f_{v, 1}\} + 1\)
建树
\(f_{u, j} = \max\{f_{v, k} + f_{u, j - k}\}\)
实际上是背包处理所有儿子 再将这些儿子合并
(资料来自网络)
翻到了四种 摘录了两种
背包属于泛化物品 合并两个泛化物品的时间复杂度是 \(O(n^2)\) 的 在树上背包中 就是一个点的每个子树的关系 对于子树的合并 有了树上背包的转移方程
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v; if(v == pre) continue;
dfs(v, u);
for(int j = m; j >= c[u]; j--)
for(int k = 0; k <= j - c[u]; k++)
f[u][j] = Max(f[u][j], f[u][j - k] + f[v][k]);
}
优化:
\(f_{u_s, j}\) 表示以 \(u\) 为根 第 \(s\) 个儿子的所有子节点和前 \(s - 1\) 个儿子构成的背包占用 \(j\) 的容量时最大价值
由于深搜对于树的遍历顺序 一个点的儿子一定先于这个点被处理
在处理每个节点 \(v\) 时 将 \(f_u\) 赋值给 \(f_v\) 此时的 \(f_v\) 表示的就是 \(v\) 之前的所有 \(u\) 的子节点加上原本意义上的 \(f_v\) 其实就是上面的状态
转移 \(f_{u, j} = \max\{f_{v, j - c_v} + val_v \}\)
相当于 \(01\) 背包的转移
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v; if(v == pre) continue;
for(int j = 0; j <= m; j++) f[v][j] = f[u][j];
dfs(v, u);
for(int j = c[v]; j <= m; j++) f[u][j] = Max(f[u][j], f[v][j - c[v]] + val[v]);
}
当在以 \(u\) 为根的子树上选择时 选择的物品最大容量不会超过 \(size_u\) 枚举以子节点 \(v\) 为根的子树全部能选的容量时 在子树中选择的物品最大容量不会超过 \(size_v\)
严格的证明并不会
复杂度均摊 \(O(nm)\)
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v; if(v == pre) continue;
dfs(v, u);
for(int j = Min(siz[u], m); j; --j)
for(int k = Min(siz[v], m - j + 1); k; --k)
f[u][j + k] = Max(f[u][j + k], f[u][j] + f[v][k]);
siz[u] += siz[v];
}
题目
给定一棵 \(n\) 个点的树 每个点有一个权值 一条边两端至少选一个点 问最大收益
同上面的题目
至多选取 \(k\) 个点
所以多了一个容量 变成了一个背包 多维护一维容量
\(f_{i, j, 0/1}\) 表示 到 \(i\) 点 选择 \(j\) 个点时 是否选该点
\(f_{u, j, 1} = \max \{\max\{f_{v, k, 1}, f_{v, k, 0}\} + f_{u, j - k, 1}\} + v_u\)
\(f_{u, j, 0} = \max \{f_{v, k, 1} + f_{u, j - k, 0}\}\)
强制 \(u\) 点选
(数组中小的一维放到外面可以带来常数上的优化)
优化:
记一个子树大小
浪费时间的背包合并
for(int i = siz[u]; i >= 0; i--)
for(int j = siz[v]; j >= 0; j--)
{
f[u][i + j][0] = Max(f[u][i + j][0], f[u][i][0] + f[v][j][1]);
f[u][i + j][1] = Max(f[u][i + j][1], f[u][i][1] + Max(f[v][j][0], f[v][j][1]));
}
siz[u] += siz[v];
复杂度从 \(O(n^3)\) 降到 \(O(n^2)\)
树形背包的上下界优化
两遍 \(dfs\)
结论 距离一个点最远的点为树的直径上的一个点
树形 \(dp\)
\(f_{u, 0} = \sum \max\{f_{v, 0}, f_{v, 1} \}\)
\(f_{u, 1} = \sum f_{v, 0} + 1\)
给出一颗 \(n\) 个点的树 找一个点满足该点为根时 所有点的深度之和最大
换根 \(dp\)
/*
Time: 5.4
Worker: Blank_space
Source: P3478 [POI2008]STA-Station
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define ll long long
/*--------------------------------------头文件*/
const int C = 1e6 + 7;
/*------------------------------------常量定义*/
int n, id;
ll f[C], siz[C], sum;
struct edge {int v, nxt;} e[C << 1];
int head[C], ecnt;
/*------------------------------------变量定义*/
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
/*----------------------------------------快读*/
void add_edge(int u, int v) {e[++ecnt] = (edge){v, head[u]}; head[u] = ecnt;}
void dfs1(int u, int pre) {
siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v; if(v == pre) continue;
dfs1(v, u); siz[u] += siz[v]; f[u] += f[v] + siz[v];
}
}
void dfs2(int u, int pre) {
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v; if(v == pre) continue;
f[v] = f[u] + n - 2 * siz[v];
if(sum < f[v]) sum = f[v], id = v; dfs2(v, u);
}
}
/*----------------------------------------函数*/
int main() {
n = read();
for(int i = 1; i < n; i++)
{
int x = read(), y = read();
add_edge(x, y); add_edge(y, x);
}
dfs1(1, 0); dfs2(1, 0); printf("%d", id);
return 0;
}
给定一个 \(n\) 个点 \(n\) 条边的图 每个点有一个出边 在图中删去若干点 使所有未删去的点至少有一条入边来自删去的点 求选取的点的最小数量
注意到这是一个基环内向树 题中每个点的出边都为 \(1\) 这是一个基环树森林 考虑反向建边 对于每一个点 该点删 或者是该点至少一个儿子被删
\(f_{i, 0/1}\) 表示到以 \(i\) 点时 以 \(i\) 点为根的子树中 \(i\) 点 \(1\) 删与 \(0\) 不删至少需要保留多少个点
删掉一条边 \(x \to y\) 图变为树 如果 \(x\) 不保留 删掉这条边不影响答案 否则 \(x\) 一定保留且 \(f_{y, 0}\) 初始化为 \(0\)
两次 \(dp\) 取最优
我推的 \(dp\) 式子 :
\(f_{u, 1} = \sum \max\{f_{v, 0}, f_{v, 1}\}\)
\(f_{u, 0} = \sum \max\{f_{v, 0}, f_{v, 1} \} + d + 1\)
\(d = \max\{f_{v, 1} - f_{v, 0} \}\)
状态不太一样 不清楚正确性
给出的式子
\(f_{u, 0} = \sum \max \{f_{v, 0}, f_{v, 1} \}\)
\(f_{u, 1} = \max \sum_{v \ne s} \max\{f_{v, 0}, f_{v, 1} \} + f_{s, 0} + 1\)
贪心解法
从下往上贪 不选叶子 选父亲 最后环上的点选一半
给出一棵树 每条边有颜色 问从哪些点出发不存在一条包含两条同色边的路径
先 \(dp\) 从每个点向下的子树内是否存在这样的路径
然后再从上往下 \(dp\) 一遍 更新所有点向父节点走是否存在非法路径
注意到若一个点至少有两条相邻的同色边 则同色边指向的子树内的点都不可行
将这样的点标为关键点 这样的边断掉 若最后所有关键点都在一个联通块内则可行 联通块内的所有点都是可行解
有一个 \(n\) 个点的完全图 每条边的权值为 \(y\) 选择一个生成树 将所有边权改为 \(x\) 求最短的哈密顿回路
一个回路通过图中每一个顶点一次 称这个环为哈密顿回路
若 \(x \geq y\) 特判菊花图 否则一定有一种方案只走 \(y\) 边
若 \(x < y\) 则要在树上选尽可能多的边 使得每个点的度数最多为 \(2\) 树形 \(dp\)
void dfs(int u) {
for(int i = 1; i <= k; i++) dfs(s[i]);
for(int i = 1; i <= k; i++)
{
int g[3];
g[0] = f[u][0]; g[1] = f[u][1]; g[2] = f[u][2];
f[u][0] = g[0] + Max(f[s[i]][0], f[s[i]][1], f[s[i]][2]);
f[u][1] = Max(g[1] + Max(f[s[i]][0], f[s[i]][1], f[s[i]][2]), g[0] + Max(f[s[i]][0], f[s[i]][1]) + 1);
f[u][2] = Max(g[2] + Max(f[s[i]][0], f[s[i]][1], f[s[i]][2]), g[1] + Max(f[s[i]][0], f[s[i]][1]) + 1);
}
}
ans = Max(f[1][0], f[1][1], f[1][2]);
或者贪心求树的最小路径覆盖
略
给定一棵 \(n\) 个点的数 从 \(1\) 到 \(n\) 标号 选择 \(k\) 个点 需要选择一些边使得这 \(k\) 个点通过选择的边联通 目标是使得选择的边数最少
计算对于所有选择 \(k\) 个点的情况最小选择边数的总和为多少
枚举每条边 若这条边两侧都有点被选中 对答案贡献 \(1\) 统计情况时补集转化 求全部 \(k\) 个点都在某一边时的情况数 计算组合数
预处理阶乘和组合数要用的逆元
深搜对于每个点统计答案
/*
Time: 5.4
Worker: Blank_space
Source: treecnt
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define int long long
#define Abs(x) ((x) < 0 ? -(x) : (x))
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
int n, k, f[B], siz[B], ans;
struct edge {int v, nxt;} e[B << 1];
int head[B], ecnt;
/*------------------------------------变量定义*/
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘) {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
/*----------------------------------------快读*/
void add_edge(int u, int v) {e[++ecnt] = (edge){v, head[u]}; head[u] = ecnt;}
int power(int a, int b, int res = 1) {for(; b; a = a * a % mod, b >>= 1) if(b & 1) res = res * a % mod; return res;}
int C(int n, int m) {return n < m ? 0 : f[n] * power(f[m], mod - 2) % mod * power(f[n - m], mod - 2) % mod;}
void dfs(int u, int pre) {
siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v; if(v == pre) continue;
dfs(v, u); siz[u] += siz[v];
ans = ((ans + C(n, k) - C(siz[v], k) - C(n - siz[v], k)) % mod + mod) % mod;
}
}
/*----------------------------------------函数*/
signed main() {
n = read(); k = read(); f[0] = f[1] = 1;
for(int i = 2; i <= n; i++) f[i] = f[i - 1] * i % mod;
for(int i = 1; i < n; i++)
{
int x = read(), y = read();
add_edge(x, y); add_edge(y, x);
}
dfs(1, 0); printf("%lld", ans);
return 0;
}
给定 \(n\) 个节点的树 有 \(m\) 个特殊位置 任选位置出发与结束 经过 \(m\) 个点中随机给定的 \(k\) 个点的最短路程
求期望经过随机 \(k\) 个点要走的距离 答案对 \(998244353\) 取模
...
略
此下 后期补充
原文：https://www.cnblogs.com/blank-space-/p/14730468.html