// 显然：染色的数量越大，A越容易获胜
// 二分，判定性问题
// 设 f[u] 表示在 u 的子树中(不包括 U)，还需要染色的点数
// f[u] = sum(f[son]+1) - mid;
// +1， 是包括 son 身，染色 mid 个， -mid;
//f[u] = max(f[u] , 0) , 不能为负数
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
const int M = N * 2;
#define int long long
int n, f[N];
int head[N], ver[M], nxt[M], tot;
int mid;
void add(int u, int v) {
++tot;
ver[tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
f[u] = 0; // 优化，只初始化用到的节点
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (v == fa) continue;
dfs(v, u);
f[u] += f[v] + 1;
}
f[u] = max(f[u] - mid, 0LL);
}
signed main() {
cin >> n;
if (n == 0) {
cout << 0;
return 0;
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
add(u, v), add(v, u);
}
// 可染色的点的数量范围为 [1 , n-1]
int l = 1, r = n - 1, ans = 0;
while (l <= r) {
mid = (l + r) / 2;
// memset(f, 0, sizeof f);
dfs(1, 0);
if (!f[1])
ans = mid, r = mid - 1;
else
l = mid + 1;
}
cout << ans;
return 0;
}
// 人: 建造， 维护
// 两个井， 建造， a[i] , 维护 b[i]
// a[i] , b[i] a[j] b[j]
// 5 2 6 4
// 先 i 后 j : 5 + 3 = 8
// 先 J 后 i : 6 + 3 = 9
// a[i] - b[i] > a[j] - b[j]
//
// f[i] : 以 i 为根，需要的最少人力
// f[i] = max(f[i] , f[v] + cur) cur：之前维护的人数
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = N * 2;
#define int long long
int n;
int head[N], ver[M], nxt[M], tot;
int ans;
int d[N]; // d[i] 深度为 i 的点的个数
int f[N]; // f 两个深度相同的点的组合数
int g[N]; // 一个深度相同的点的组合数
void add(int u, int v) {
++tot;
ver[tot] = v;
nxt[tot] = head[u] ;
head[u] = tot;
}
int maxx;
// 求到所有点的深度
void dfs(int u, int fa, int dep) {
d[dep]++;
maxx = max(maxx, dep);
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
dfs(v, u, dep + 1);
}
}
signed main() {
cin >> n;
for (int i = 2; i <= n; i++) {
int u, v;
cin >> u >> v;
add(u, v), add(v, u);
}
// 枚举所有的起点
for (int u = 1; u <= n; u++) {
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
for (int i = head[u]; i; i = nxt[i]) {
memset(d, 0, sizeof d);
int v = ver[i];
dfs(v, u, 1);
// 对于当前子树 v
// 和之前的子树匹配
// 枚举所有的深度
//int d[N]; // d[i] 深度为 i 的点的个数
//int f[N]; // f 两个深度相同的点的组合数
// int g[N]; // 一个深度相同的点的组合数
for (int k = 1; k <= maxx ; k++) {
ans += f[k] * d[k];
f[k] += g[k] * d[k];
g[k] += d[k];
}
}
}
cout << ans;
return 0;
}
// 一个节点而言
// 自己建立， 子节点建立
// 父节点建立
// f[u][0] :自己建立，
// f[u][0] += min(f[son][0] , f[son][1],f[son][2])
// f[u][2] :父节点建立
// f[u][2] += min(f[son][0], f[son][1])
// f[u][1] 子节点建立, 很多子节点，
// 最优子节点 t，
// f[u][1] += f[t][0] +sum( min(f[son][0] , f[son][1])) ,son 排除 t
// 怎么求最优子节点 t , v
// f[t][0] +sum( min(f[son][0] , f[son][1])) + min(f[t][0] , f[t][1]) - min(f[t][0] , f[t][1])
// f[v][0] +sum( min(f[son][0] , f[son][1])) + min(f[v][0] , f[v][1]) - min(f[v][0] , f[v][1])
//
// 化简为
// f[t][0] - min(f[t][0] , f[t][1])
// f[v][0] - min(f[v][0] , f[v][1])
// 所以 t 是 f[t][0] - min(f[t][0] , f[t][1]) 的最小值
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
const int M = N * 2;
int n;
int head[N], ver[M], nxt[M], tot;
int f[N][3];
void add(int u, int v) {
++tot;
ver[tot] = v ;
nxt[tot] = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
int t = 0;
f[u][0] = 1;
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (v == fa) continue;
dfs(v, u);
f[u][0] += min({f[v][0], f[v][1], f[v][2]});
f[u][2] += min(f[v][0], f[v][1]);
// 找最优子儿子
if ((f[t][0] - min(f[t][0], f[t][1])) > (f[v][0] - min(f[v][0], f[v][1])))
t = v;
}
f[u][1] = f[t][0];
for (int i = head[u] ; i; i = nxt[i]) {
int v = ver[i];
if (v == fa || v == t)
continue;
f[u][1] += min(f[v][0], f[v][1]);
}
}
int main() {
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
add(u, v), add(v, u);
}
f[0][0] = 1e9;
dfs(1, 0);
cout << min(f[1][0], f[1][1]);
return 0;
}
L
// f[u] 以 u 为根的最大高度
// f[u] = max(f[u] , f[v]) , 子树的高度
// f[u] += son[u]
void dfs(int u, int fa) {
f[u] = son[u] = 0;
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
son[u]++;
dfs(v, u);
f[u] = max(f[u], f[v]);
}
f[u] += son[u];
}
K
void dfs(int u, int fa) {
// 边是负收益 ，叶子节点是正收益
if (u > n - m) { // 证明是叶子节点
f[u][1] = a[u];
siz[u] = 1;
return ;
}
//不是叶子节点
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
int w = edge[w];
if (v == fa)
continue;
dfs(v,u);
siz[u] += siz[v];
// 背包
for (int j = siz[u] ; j >= 0 ; j--) {
// 分配给当前 v 子树多少人
for (int k = 0 ; k <= min( j, siz[v]) ; k++)
// 边权是负数
f[u][j] = max(f[u][j], f[v][k] + f[u][j - k] - w);
}
}
}
void init() { // f 数组初始化
memset(f, 0xcf, sizeof f);
for (int i = 1; i <= n; i++)
f[i][0] = 0;
}
void print() {
for (int i = m ;; i--)
if (f[1][i] >= 0) {
cout << i;
return ;
}
}
J
int res;
void dfs(int u, int fa) {
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
int w = edge[i];
if (v == fa)
continue;
dfs(v, u);
f[u] = max(f[u], f[v] + w);
}
// 统一所有子树的高度
for (int i = head[u] ; i; i = nxt[i]) {
int v = ver[i];
int w = edge[i];
if (v == fa)
continue;
res += f[u] - (f[v] + w); // 需要调整的地方
}
}
H
f[i][0] i 节点不部署
f[i][1] i 节点部署
f[i][1] = c[i]
状态转移：
f[i][1] += min(f[v][0] , f[v][1])
// 保证每一条路都监测到
f[i][0] += f[v][1]
G
f[i][0] i 节点不参加
f[i][1] i 节点参加
f[i][1] = c[i]
状态转移：
f[i][0] += max(f[v][0] ,f[v][1])
f[i][1] += f[v][0]
F
// f[i][0] i 节点不拜访
// f[i][1] i 节点拜访
f[i][0] += max(f[v][0] , f[v][1])
f[i][1] += f[v][0]
初始化
f[i][1] =1
E
void dfs(int u, int fa) {
siz[u] = 1 ;
int t = 1; // 记录 根以及 叶子节点的数量
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
dfs(v, u);
siz[u] += siz[v];
if (siz[v] == 1)
t++;
else // 如果不是叶子节点，递归
f[u] += f[v];
}
f[u] += t / 2;
}
// 对于每个树枝，剪或者不剪
// 树上背包
// f[i] 以 i 为根的树的某个状态
// f[i][j] 以 i 为根，保留 j 根树枝的最多苹果数
//
// f[i][j] = max(f[i][j] , f[y][k] + f[i][j-k-1] +z) （ 0<=k<= min(j-1 , siz[y]-1)）
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
const int M = N * 2;
int n, m;
int f[N][N];
int head[N], ver[M], nxt[M], edge[M], tot;
int siz[N];
void add(int u, int v, int w) {
++tot;
ver[tot] = v;
nxt[tot] = head[u];
edge[tot] = w;
head[u] = tot;
}
void dfs(int u, int fa) {
siz[u] = 1;
for (int i = head[u] ; i; i = nxt[i]) {
int v = ver[i];
int w = edge[i];
if (v == fa)
continue;
dfs(v, u);
siz[u] += siz[v];
// 01 背包 , 以u 为根，
for (int j = min(m, siz[u] - 1) ; j; j--) {
// 新的子树 v , 考虑给 v几个树枝
for (int k = 0; k <= min(j - 1, siz[v] - 1) ; k++)
// u 到 v 还有一条边
f[u][j] = max(f[u][j], f[v][k] + f[u][j - k - 1] + w);
}
}
}
int main() {
cin >> n >> m;
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);
cout << f[1][m];
return 0;
}
E
// f[u][0] u 位置不放置士兵
// f[u][1] u 位置放置士兵
// u 和 v 之间有一条边，u 没有士兵，v必须有
// f[u][0] += f[v][1]
// u 这个点已经有了， v 有没有无所谓
//f[u][1] += min(f[v][0] , f[v][1])
A
// f[i][2] 以 i 为根的子树的最大值，0 代表不来， 1 代表来
// f[i][2] i 的所有子节点
// 上司不来， 下属可以来或者不来
// f[i][0] += max(f[son[i]][0] , f[son[i]][1])
// 上司来， 下属不能来
// f[i][1] += f[son[i]][0]
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
const int M = N * 2;
int n, r[N];
int head[N], ver[M], nxt[M], tot;
int f[N][2];
void add(int u, int v) {
++tot;
ver[tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
f[u][1] = r[u];
// 遍历所有子节点
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
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() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> r[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
add(u, v), add(v, u);
}
dfs(1, 0);
cout << max(f[1][0], f[1][1]);
return 0;
}
B
// f[i][j] 以 i 为根,选择 j 门课程
// 的最大学分
// f[i][j] = max(f[i][j-k] + f[v][k])
// 森林， 加一个 root 节点
// m ，加上root 节点， m+1 门课
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
const int M = N * 2;
int a[N];
int f[N][N];
int n, m;
int siz[N];
int head[N], ver[M], nxt[M], tot;
void add(int u, int v) {
++tot;
ver[tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
f[u][1] = a[u]; // 学一门，只能是学自己
siz[u] = 1;
for (int i = head[u] ; i; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
dfs(v, u);
siz[u] += siz[v];
// 分组背包
for (int j = min(m, siz[u]) ; j >= 1; j-- ) {
// u 这个点是必须放的 -1
for (int k = 0 ; k <= min(j - 1, siz[v]) ; k++)
f[u][j] = max(f[u][j], f[v][k] + f[u][j - k]);
}
}
}
int main() {
cin >> n >> m;
m++; // root
for (int i = 1 ; i <= n; i++) {
int x;
cin >> x >> a[i];
// 如果 x 为0，直接当做根节点，不用管
add(x, i), add(i, x);
}
dfs(0, -1);
cout << f[0][m];
return 0;
}
T
// 换根DP
// f[v] = f[u] - siz[v]-n - siz[v]
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = N * 2;
#define int long long
int n;
int siz[N], dep[N], f[N];
int head[N], ver[M], nxt[M], tot;
void add(int u, int v) {
++tot;
ver[tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
siz[u] = 1;
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
dfs(v, u);
siz[u] += siz[v];
}
}
void dp(int u, int fa) {
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
if (v == fa)
continue;
f[v] = f[u] - 2 * siz[v] + n;
dp(v, u);
}
}
signed main() {
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];
dp(1, 0);
int res = 1;
for (int i = 2; i <= n; i++)
if (f[i] > f[res])
res = i;
cout << res;
return 0;
}
