「做题记录」树上问题选做
stripe_python · · 算法·理论
P4362 [NOI2002] 贪吃的九头龙
给出一棵节点数为
n 的有根树,根节点为1 ,边带权。你需要将这棵树m 染色,满足与根节点同色的节点数恰为k 。代价为两端点颜色相同的边的边权和,最小化代价并输出,或报告无解。
:::::success[题解]
不妨设根节点的颜色为
- 当
m>2 时,容易构造所有边端点颜色不同的情况,比如按深度对m-1 取模染色。 - 当
m=2 时,森林中所有边都有贡献。
据此设计树形 DP:
其中
注意合并 DP 时需要新建数组,不然会覆盖原本的取值。无解容易判断。
| 正确的实现为树形背包复杂度,复杂度 |
|---|
:::::info[代码]
const int N = 305, inf = 0x3f3f3f3f;
int n, m, k;
vector<pair<int, int>> e[N];
int sz[N], f[2][N][N];
void dfs(int u, int fa) {
f[0][u][0] = 0, f[1][u][1] = 0, sz[u] = 1;
for (auto [v, w] : e[u]) {
if (v == fa) continue;
dfs(v, u);
vector<int> f0(N, inf), f1(N, inf);
for (int i = min(sz[u], k); i >= 0; i--) {
for (int j = min(sz[v], k - i); j >= 0; j--) {
chkmin(f0[i + j], f[0][u][i] + f[0][v][j] + (m == 2) * w);
chkmin(f0[i + j], f[0][u][i] + f[1][v][j]);
chkmin(f1[i + j], f[1][u][i] + f[0][v][j]);
chkmin(f1[i + j], f[1][u][i] + f[1][v][j] + w);
}
}
sz[u] += sz[v];
copy(f0.begin(), f0.end(), f[0][u]), copy(f1.begin(), f1.end(), f[1][u]);
}
}
void _main() {
cin >> n >> m >> k;
if (n - k < m - 1) return cout << -1, void();
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
memset(f, 0x3f, sizeof(f)), dfs(1, -1);
cout << f[1][1][k];
}
:::::
P9669 [ICPC 2022 Jinan R] DFS Order 2
给出一棵节点数为
n 的有根树,根节点为1 。对于每个x=1,2,\cdots,n 和p=1,2,\cdots,n 求出:在所有 DFS 序中,x 位于 DFS 序第p 位的方案数。对998244353 取模。
:::::success[题解]
根据 DFS 的规则,访问
注意到总的 DFS 序数目为
对于祖先节点
我们需要知道子树大小总和为
分析向
| 得到以上信息后,将 |
|---|
:::::info[代码]
const int N = 505;
int n, sz[N], dep[N];
vector<int> e[N];
mint fac[N], ifac[N], h[N][N], ans[N][N];
void dfs1(int u, int fa) {
sz[u] = 1;
for (int v : e[u]) {
if (v == fa) continue;
dep[v] = dep[u] + 1, dfs1(v, u), sz[u] += sz[v];
}
}
void dfs2(int u, int fa) {
if (e[u].size() == 1 && e[u][0] == fa) return;
int m = u == 1 ? e[u].size() : e[u].size() - 1;
vector<vector<mint>> f(m + 5, vector<mint>(sz[u] + 5));
f[0][0] = 1;
int sum = 0;
for (int v : e[u]) {
if (v == fa) continue;
sum += sz[v];
for (int i = m; i >= 1; i--) {
for (int j = sum; j >= sz[v]; j--) f[i][j] += f[i - 1][j - sz[v]];
}
}
for (int v : e[u]) {
if (v == fa) continue;
auto g = f;
for (int i = 1; i <= m; i++) {
for (int j = sz[v]; j <= sum; j++) g[i][j] -= g[i - 1][j - sz[v]];
}
vector<mint> p(sum + 5);
for (int j = 0; j <= sum - sz[v]; j++) {
for (int i = 0; i < m; i++) p[j] += g[i][j] * fac[i] * fac[m - i - 1] * ifac[m];
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum - sz[v] && i + j <= n; j++) h[v][i + j] += h[u][i] * p[j];
}
dfs2(v, u);
}
}
void _main() {
fac[0] = ifac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i];
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
h[1][0] = 1, dfs1(1, -1), dfs2(1, -1);
mint t = fac[e[1].size()];
for (int i = 2; i <= n; i++) t *= fac[e[i].size() - 1];
for (int u = 1; u <= n; u++) {
for (int i = 0; i <= n; i++) {
int pos = 1 + dep[u] + i;
if (pos <= n) ans[u][pos] += h[u][i] * t;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) cout << ans[i][j] << ' ';
cout << '\n';
}
}
:::::
CF2068D Morse Code
给出
n 个实数f_i 。你需要为每个i 分配一个字符串s_i ,使得不存在i \ne j 满足s_i 是s_j 的前缀。字符集为\{\tt{.},\tt{-}\} 。其中\tt{.} 的代价为1 ,\tt{-} 的代价为2 ,字符串的代价为其中字符代价之和。设
s_i 的代价为c_i ,最小化\sum\limits_{i=1}^n f_ic_i ,构造方案并输出。
:::::success[题解]
你说的对,但
下面称
我们肯定不能显式建立 01-Trie。因此考虑直接搜索,逐层构建 01-Trie。接下来有一个观察:
因此,按
用四元组
状态数是
对于三元组
这里状态数为
:::::
:::::info[代码]
const int N = 255;
const double inf = 1e18;
using node = pair<double, int>;
int n; node a[N];
double suf[N];
string ans[N];
int vis[N][N][N], opt[N][N][N];
double mem[N][N][N];
double dfs(int k, int cur, int nxt) {
if (k == n) return 0;
if (cur == 0 && nxt == 0) return inf;
if (vis[k][cur][nxt] == 1) return inf;
if (vis[k][cur][nxt] == 2) return mem[k][cur][nxt];
vis[k][cur][nxt] = 1;
double res = inf; int p = -1;
for (int i = 0; i <= min(n - k, cur); i++) {
int nk = k + cur - i;
double cost = suf[nk + 1] + dfs(nk, min(nxt + i, n - nk), min(i, n - nk));
if (cost < res) res = cost, p = i;
}
vis[k][cur][nxt] = 2;
return opt[k][cur][nxt] = p, mem[k][cur][nxt] = res;
}
void work() {
vector<string> cur = {""}, nxt;
for (int k = 0; k < n; ) {
int i = opt[k][min<int>(cur.size(), n - k)][min<int>(nxt.size(), n - k)];
vector<string> nnxt;
for (int j = 0; j < i; j++) {
nxt.emplace_back(cur[j] + '.');
nnxt.emplace_back(cur[j] + '-');
}
int cnt = min<int>(cur.size(), n - k) - i;
for (int j = 0; j < cnt; j++) {
ans[a[k + j + 1].second] = cur[i + j];
}
k += cnt, cur.swap(nxt), nxt.swap(nnxt);
}
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i;
sort(a + 1, a + n + 1, greater<node>());
for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] + a[i].first;
dfs(0, 1, 0), work();
for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}
:::::
P9527 [JOIST 2022] 洒水器 / Sprinkler
给出一棵
n 个节点的无根树,点有点权a_i 。q 次操作:
- 给出
u,k,x ,将距离u 不超过k 的点的点权乘x 。- 给出
u ,查询u 的点权。对给出的模数取模,不保证模数为质数。
:::::success[题解]
在树上每个节点维护若干标记:将
修改时对这些标记进行更新:
标记下传很困难,因此永久化。查询时需要跳父亲来得到标记。也只会跳
| 这个做法可以做到不重不漏。复杂度 |
|---|
:::::info[代码]
const int N = 2e5 + 5;
int n, _mod, q, fa[N];
vector<int> e[N];
mint a[N], tag[41][N];
void dfs(int u) {
for (int v : e[u]) {
if (v == fa[u]) continue;
fa[v] = u, dfs(v);
}
}
void _main() {
cin >> n >> _mod, mint::set_mod(_mod);
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
for (int i = 1; i <= n; i++) cin >> a[i];
fa[1] = -1, dfs(1);
for (int i = 0; i <= 40; i++) fill(tag[i], tag[i] + n + 1, 1);
cin >> q;
for (int opt, u, k, x; q--; ) {
cin >> opt >> u;
if (opt == 1) {
cin >> k >> x;
for (int i = 0; i <= k; i++, u = fa[u]) {
if (fa[u] == -1) {
for (int d = 0; d <= k - i; d++) tag[d][u] *= x;
break;
}
tag[k - i][u] *= x;
if (k - i - 1 >= 0) tag[k - i - 1][u] *= x;
}
} else {
mint res = a[u];
for (int i = 0; i <= 40 && u != -1; i++, u = fa[u]) res *= tag[i][u];
cout << res << '\n';
}
}
}
:::::
P9755 [CSP-S 2023] 种树
给定一棵节点树为
n 的有根树,根节点为1 。每个节点上有一个任务。每个时刻,你可以标记一个节点,要求这个节点为根或其父亲已被标记。对于被标记的节点,在第
x 个时刻任务的完成度将会增加\max(1,b_i+x\times c_i) 。目标为所有节点i 上任务的完成度\ge a_i 。初始时任务完成度均为0 。求完成所有任务的最小时间。
:::::success[题解]
考虑特殊性质 A,即
由于答案取决于每个任务的最晚完成时间,因此考虑调整后一定不优,可以说明这个做法的正确性。
上述算法直观的实现是树剖线段树,复杂度
接下来考虑特殊性质 B,即链的情形。考虑二分答案
- 若
c_x \ge 0 ,此时增长量单调增,套等差数列求和即得f(x,l,r)=(r-l+1) \times b_x+\frac{(r-l+1)(l+r)}{2} c_x 。 - 否则需要分类讨论。列不等式
b_x+k\times c_x \le 1 得k_{\min} =\lfloor \frac{1-b_x}{c_x} \rfloor ,表示在时刻[k,+\infty) 中增长量恒为1 。- 若
k < l ,则增长量恒为1 ,此时f(x,l,r)=r-l+1 ; - 若
k>r ,则增长量恒为等差数列,与c_x\ge 0 的式子相同:f(x,l,r)=(r-l+1)\times b_x+\frac{(r-l+1)(l+r)}{2} c_x ; - 若
k \in [l,r] ,则增长量分为等差数列段和常数段。分段计算知f(x,l,r)=(k-l+1) \times b_x+\frac{(k-l+1)(l+k)}{2}c_x+r-k 。
- 若
可以做到
考虑将 A & B 的做法结合起来。我们二分答案
| 按照 |
|---|
:::::info[代码]
const int N = 1e5 + 5;
int n, fa[N], tag[N];
vector<int> e[N];
void dfs(int u) {
for (int v : e[u]) if (v != fa[u]) fa[v] = u, dfs(v);
}
i64 a[N], b[N], c[N], t[N];
i128 f(int x, i128 l, i128 r) {
if (c[x] >= 0) return (r - l + 1) * b[x] + (r - l + 1) * (l + r) / 2 * c[x];
i64 k = (1 - b[x]) / c[x];
if (k < l) return r - l + 1;
if (k > r) return (r - l + 1) * b[x] + (r - l + 1) * (l + r) / 2 * c[x];
return (k - l + 1) * b[x] + (k - l + 1) * (l + k) / 2 * c[x] + r - k;
}
bool check(int x) {
for (int i = 1; i <= n; i++) {
if (f(i, 1, x) < a[i]) return false;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (f(i, mid, x) >= a[i]) l = mid + 1, t[i] = mid;
else r = mid - 1;
}
}
fill(tag + 1, tag + n + 1, 0);
vector<int> vec(n); iota(vec.begin(), vec.end(), 1);
sort(vec.begin(), vec.end(), [](int x, int y) -> bool {
return t[x] < t[y];
});
int cur = 0;
for (int i : vec) {
if (tag[i]) continue;
stack<int> st;
for (int j = i; j != -1 && !tag[j]; j = fa[j]) st.emplace(j);
while (!st.empty()) {
int u = st.top(); st.pop();
if (++cur > t[u]) return false;
tag[u] = true;
}
} return true;
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
fa[1] = -1, dfs(1);
int l = 0, r = 1e9, res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) res = mid, r = mid - 1;
else l = mid + 1;
} cout << res;
}
:::::
P5290 [十二省联考 2019] 春节十二响
给出一棵以
1 为根的有根树,节点数为n ,点带权a_i 。你需要将这些节点划分为若干个集合S_1,S_2,\cdots,S_k ,满足集合内部不存在祖先—后代关系。最小化\sum\limits_{i=1}^k \max\limits_{u \in S_i} a_u 并输出。
:::::success[题解]
对于点
注意到
接下来证明局部最优不会影响祖先答案。将不升序列
子树
| 直接模拟即可 |
|---|
:::::info[代码]
const int N = 2e5 + 5;
int n, a[N];
vector<int> e[N];
priority_queue<int> q[N];
void join(int u, int v) {
if (q[u].size() < q[v].size()) swap(q[u], q[v]);
vector<int> vec;
while (!q[v].empty()) {
vec.emplace_back(max(q[u].top(), q[v].top()));
q[u].pop(), q[v].pop();
}
for (int i : vec) q[u].emplace(i);
}
void dfs(int u) {
for (int v : e[u]) dfs(v), join(u, v);
q[u].emplace(a[u]);
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int v = 2, u; v <= n; v++) cin >> u, e[u].emplace_back(v);
dfs(1); i64 res = 0;
while (!q[1].empty()) res += q[1].top(), q[1].pop();
cout << res;
}
:::::
P5521 [yLOI2019] 梅深不见冬
给出一棵节点数为
n 的有根树,根节点为1 ,带点有点权a_u 。你初始持有
f_u 个物品,位于节点1 。你可以在树上进行游走,可以选择进入一个未进入的子节点,或者回到父节点。你需要在每个节点上放置若干物品。对于非叶节点
u ,允许在其上放置物品的条件为:每个子节点v 的物品数都恰好为a_v 。你可以在任意时刻回收任意节点上的物品,且不需要走到对应点。
对于
u=1,2,\cdots,n ,求出在节点u 上放置a_u 个物品所需的f_u 的最小值。
:::::success[题解]
考虑树形 DP,设
根据木桶原理这里做的是 chkmax。前面这个求和式表示之前回收的物品总数,容易前缀和维护。
现在考虑如何对儿子
记前面的和式为
- 先
x 后y :- 处理
x 时的需求量为S+f_x 。 - 处理
y 时,S \gets S+a_x ,故需求量S+a_x+f_y 。 - 故局部峰值为
\max(S+f_x,S+a_x+f_y)=S+\max(f_x,a_x+f_y) 。
- 处理
- 先
y 后x 同理,得局部峰值S+\max(f_y,a_y+f_x) 。
令
根据
得证,按
| 复杂度 |
|---|
:::::info[代码]
const int N = 1e5 + 10;
int n, a[N];
vector<int> e[N];
i64 f[N];
void dfs(int u) {
for (int v : e[u]) dfs(v);
sort(e[u].begin(), e[u].end(), [](int x, int y) -> bool {
return f[x] - a[x] > f[y] - a[y];
});
i64 sum = 0;
for (int v : e[u]) f[u] = max(f[u], sum + f[v]), sum += a[v];
f[u] = max(f[u], sum + a[u]);
}
void _main() {
cin >> n;
for (int i = 2, x; i <= n; i++) cin >> x, e[x].emplace_back(i);
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(1);
for (int i = 1; i <= n; i++) cout << f[i] << ' ';
}
:::::
P3574 [POI 2014] FAR-FarmCraft
给出一棵
n 个点的有根树,根节点为1 。你从根节点开始游走,走过一条边的代价为1 ,必须经过每条边恰好两次。每个点有点权
a_i ,当你游走到该点时,该点上会开始一个时长为a_i 的任务。最终回到根节点后,开始一个时长为a_1 的任务。最小化所有点完成任务的时间并输出。
:::::success[题解]
考虑树形 DP,记
关键在于确定
- 不交换:贡献为
\max(f_x+g_u+1, f_y+g_u+g_x+3) ; - 交换:贡献为
\max(f_y+g_u+1,f_x+g_u+g_y+3) 。
钦定前者更优,于是
| 这是一个严格偏序,按 |
|---|
:::::info[代码]
const int N = 5e5 + 5;
int n, a[N], f[N], g[N];
vector<int> e[N];
void dfs(int u, int fa) {
if (fa != -1) f[u] = a[u];
vector<int> vec;
for (int v : e[u]) {
if (v == fa) continue;
dfs(v, u), vec.emplace_back(v);
}
sort(vec.begin(), vec.end(), [](int x, int y) -> bool {
return f[x] - g[x] > f[y] - g[y];
});
for (int v : vec) chkmax(f[u], f[v] + g[u] + 1), g[u] += g[v] + 2;
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
dfs(1, -1);
cout << max(f[1], a[1] + g[1]);
}
:::::
ABC376G Treasure Hunting
给出一棵
n+1 个点的有根树,根节点为0 。你从根节点开始游走,只能游走到父亲已经走过的点。每个点有\frac{a_i}{\sum a} 的概率为关键点,最小化到达关键点步数的期望值并输出,对998244353 取模。多测,
\sum n \le 2 \times 10^5 ,2 秒,1024 MB。
:::::success[题解] 树上 exchange argument 模板题。
将所有概率乘上
拓扑序是合并连通块的过程,合并的顺序考虑用 exchange argument 确定。记
钦定上式
可以用并查集 + set 来维护。初始时,将所有节点加入集合,其中
每次取出最大的
| 总复杂度 |
|---|
:::::info[代码]
const int N = 2e5 + 5;
int n, p[N], fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
i64 a[N], c[N], w[N];
struct node {
i64 w, c; int id;
node(i64 x = 0, i64 y = 0, int z = 0) : w(x), c(y), id(z) {}
bool operator< (const node& a) const {
if (w * a.c != c * a.w) return w * a.c > c * a.w;
return id < a.id;
}
};
set<node> q;
void _main() {
cin >> n;
iota(fa, fa + n + 1, 0);
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= n; i++) cin >> a[i];
mint sum = accumulate(a + 1, a + n + 1, mint(0)), cost = sum;
copy(a, a + n + 1, w), fill(c, c + n + 1, 1);
c[0] = 0, w[0] = 0;
for (int i = 1; i <= n; i++) q.emplace(w[i], c[i], i);
while (!q.empty()) {
int u = q.begin()->id; q.erase(q.begin());
int v = find(p[u]);
if (v != 0) q.erase(node(w[v], c[v], v));
cost += c[v] * w[u];
c[v] += c[u], w[v] += w[u], fa[find(u)] = find(v);
if (v != 0) q.emplace(w[v], c[v], v);
}
cout << cost / sum << '\n';
}
:::::
QOJ8130 Yet Another Balanced Coloring Problem
给出两棵大小为
n,m 的有根树,根节点分别为n 和m 。保证两棵树的叶子节点均为1,2,\cdots,k 。构造一种对叶子的黑白染色方案,使得对于每棵树,每个子树中黑点与白点的数目相差不超过1 。输出方案或报告无解。多测,
\sum (n+m) \le 2 \times 10^5 ,1 秒,256 MB。
:::::success[题解] 先考虑一棵树的情形。
叶向树问题,自底向上贪心。对于当前子树中未处理的叶子,我们在新图
两棵树的情形,考虑套用上面的做法。正确性仍然显然。
| 并且可以说明,这样做一定有解。注意到每个点的度数 |
|---|
:::::info[代码]
const int N = 1e5 + 5;
int n, m;
vector<int> e1[N], e2[N], e[N];
int dfs1(int u, vector<int>* et) {
if (et[u].empty()) return u;
vector<int> vec;
for (int v : et[u]) {
int x = dfs1(v, et);
if (x != -1) vec.emplace_back(x);
}
while (vec.size() > 1) {
int x = vec.back(); vec.pop_back();
int y = vec.back(); vec.pop_back();
e[x].emplace_back(y), e[y].emplace_back(x);
}
return vec.empty() ? -1 : vec[0];
}
int col[N];
void dfs2(int u) {
for (int v : e[u]) {
if (col[v] != -1) continue;
col[v] = col[u] ^ 1, dfs2(v);
}
}
void _main() {
cin >> n >> m;
for (int i = 1; i <= max(n, m); i++) e1[i].clear(), e2[i].clear(), e[i].clear();
for (int v = 1, u; v < n; v++) cin >> u, e1[u].emplace_back(v);
for (int v = 1, u; v < m; v++) cin >> u, e2[u].emplace_back(v);
dfs1(n, e1), dfs1(m, e2);
int k = 0;
for (int i = 1; i <= min(n, m); i++) if (e1[i].empty()) k++;
fill(col + 1, col + k + 1, -1);
for (int i = 1; i <= k; i++) {
if (col[i] != -1) continue;
col[i] = 0, dfs2(i);
}
for (int i = 1; i <= k; i++) cout << (col[i] ? 'R' : 'B');
cout << '\n';
}
:::::
P7600 [APIO2021] 封闭道路
给出一棵
n 个节点的无根树,边带权。对于每个k=0,1,\cdots,n-1 求出:删去一些边使得每个点的度数\le k ,最小化删去的边权之和。
:::::success[题解] 将问题转化为最大化保留边的边权和。
首先是一个暴力 DP:记
考虑先将儿子全选
复杂度
我们注意到,度数
沿用
- 虚树外的点:权值为
w ; - 虚树内的点:权值为
g_v+w-f_v 。
| 那么只需要维护前 |
|---|
:::::info[代码]
const int N = 1e5 + 5, M = 1e9;
int n, deg[N];
vector<pair<int, int>> e[N];
int dn, fa[N], sz[N], dep[N], son[N], top[N], dfn[N], wei[N];
void dfs1(int u) {
sz[u] = 1, dfn[u] = ++dn;
for (auto [v, w] : e[u]) {
if (v == fa[u]) continue;
fa[v] = u, wei[v] = w, dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
if (son[u]) dfs2(son[u], t);
for (auto [v, w] : e[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
} return dep[u] < dep[v] ? u : v;
}
#define ls lson[rt]
#define rs rson[rt]
int tot, rt[N], lson[N << 6], rson[N << 6], cnt[N << 6];
i64 sum[N << 6];
void insert(i64 x, i64 l, i64 r, int& rt) {
if (!rt) rt = ++tot;
cnt[rt]++, sum[rt] += x;
if (l == r) return;
i64 mid = (l + r) >> 1;
if (x <= mid) insert(x, l, mid, ls);
else insert(x, mid + 1, r, rs);
}
void remove(i64 x, i64 l, i64 r, int& rt) {
if (!rt) rt = ++tot;
cnt[rt]--, sum[rt] -= x;
if (l == r) return;
i64 mid = (l + r) >> 1;
if (x <= mid) remove(x, l, mid, ls);
else remove(x, mid + 1, r, rs);
}
i64 ask(int k, i64 l, i64 r, int rt) {
if (rt == 0 || k <= 0) return 0;
if (cnt[rt] <= k) return sum[rt];
if (l == r) return l * k;
i64 mid = (l + r) >> 1;
if (cnt[rs] >= k) return ask(k, mid + 1, r, rs);
return sum[rs] + ask(k - cnt[rs], l, mid, ls);
}
bool keep[N];
vector<int> nd[N], ev[N], dr[N];
i64 f[N], g[N];
void dfs3(int u, int k) {
f[u] = g[u] = 0;
i64 sum = 0;
vector<i64> son;
for (int v : ev[u]) {
dfs3(v, k);
if (fa[v] == u && keep[v]) sum += f[v], son.emplace_back(g[v] + wei[v] - f[v]);
else sum += f[v];
}
if (keep[u]) {
for (i64 x : son) if (x > 0) insert(x, 1, M, rt[u]);
f[u] = sum + ask(k, 1, M, rt[u]), g[u] = sum + ask(k - 1, 1, M, rt[u]);
for (i64 x : son) if (x > 0) remove(x, 1, M, rt[u]);
} else {
f[u] = sum, g[u] = 0;
}
}
vector<i64> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
n = N; i64 sum = 0;
for (int i = 0; i < n - 1; i++) {
int u = U[i] + 1, v = V[i] + 1, w = W[i];
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
deg[u]++, deg[v]++, sum += w;
}
for (int u = 1; u <= n; u++) {
for (int i = 0; i < deg[u]; i++) nd[i].emplace_back(u);
dr[deg[u]].emplace_back(u);
}
dfs1(1), dfs2(1, 1);
vector<i64> ans(n); ans[0] = sum;
i64 bas = 0;
fill(keep + 1, keep + n + 1, true);
for (int k = 1; k < n; k++) {
for (int u : dr[k]) {
keep[u] = false;
for (auto [v, w] : e[u]) {
if (keep[v]) insert(w, 1, M, rt[v]);
else bas += w;
}
}
vector<int>& a = nd[k];
if (a.empty()) {
ans[k] = sum - bas;
continue;
}
sort(a.begin(), a.end(), [](int u, int v) {return dfn[u] < dfn[v];});
int len = a.size();
for (int i = 0; i < len - 1; i++) a.emplace_back(lca(a[i], a[i + 1]));
sort(a.begin(), a.end(), [](int u, int v) {return dfn[u] < dfn[v];});
a.erase(unique(a.begin(), a.end()), a.end());
for (int i = 0; i < (int)a.size() - 1; i++)
ev[lca(a[i], a[i + 1])].emplace_back(a[i + 1]);
dfs3(a[0], k);
ans[k] = sum - bas - f[a[0]];
for (int i : a) ev[i].clear();
}
return ans;
}
:::::
P3479 [POI 2009] GAS-Fire Extinguishers
给出一棵节点数为
n 的有根叶向树,根节点为1 。你需要在某些节点放置任意数量的元素,每个元素可以被分配给距离\le k 的节点,且最多分配给s 个不同节点。要求每个节点至少被分配到一个元素。最小化放置元素的总数目并输出。
::::::success[题解] 叶向树上的问题,考虑自底向上贪心。
我们声称,元素应当尽量放置在深度较小的节点上。对于节点
可以用调整法说明上述策略的正确性。假设存在最优解,将
现在将
- 对
u 点:根据定义d(x,u)=k ,必要性成立; - 对
x 子树外:假定v 处元素还覆盖了x 子树外的节点w ,则满足d(v,w)=d(v,x)+d(x,w) \le k 。移动到x 有d(x,w) \le k ,故移动不会影响x 外的节点; - 对
x 子树内:反证法,若存在y 使得其原本能被v 覆盖,但不能被x 覆盖,则其满足d(v,y )\le k \land d(x,y) > k 。根据定义,d(x,u)=k 且u 是子树内最深的未分配节点,而这里y 比u 深,矛盾。所以不存在这样的y 。
说明这一做法的正确性后,考虑设计树形 DP 来执行策略。
记
一种错误的策略为:将满足
事实上,我们只应该在如下两种情况时进行匹配:
- 在
i+j \in \{k-1,k\} 时将其匹配。因为如果再往祖先移动,就有i \gets i+1,j \gets j+1 ,此时i+j>k 失去匹配机会; - 存在
g_{k,x}>0 时,再向上走就无法处理这一需求,所以必须在x 处新建元素f_{0,x} 将其匹配。
正确性容易说明,考虑上述过程相当于贡献延后 DP,且所有余量—需求关系最终都会在根节点正确处理。
自底向上 DFS,对于当前节点
- 首先,将儿子的需求上传到
x ,距离增加1 ,并在x 处新增一个距离为0 的需求: -
- 接下来处理第一类匹配。倒序枚举
i = k,k-1,\cdots,0 ,并考虑j \in \{k-i,k-i-1\} 。匹配的数目由\min(g_{i,u},f_{j,u}) 决定。 - 在处理
i=k 后,进行第二类匹配。计算出放置元素的数目a=\lceil \frac{g_{k,u}}{s} \rceil ,然后清空g_{k,u} \gets 0 ,并将剩余元素加入f_{0,u} 。
注意在根节点处,我们需要进行剩余匹配。首先将所有
| 按照上述过程实现,可以做到 |
|---|
:::::info[代码]
const int N = 1e5 + 5;
int n, s, k;
vector<int> e[N];
i64 ans, f[21][N], g[21][N];
void dfs(int u, int fa) {
for (int v : e[u]) {
if (v == fa) continue;
dfs(v, u);
for (int i = 0; i < k; i++) f[i + 1][u] += f[i][v], g[i + 1][u] += g[i][v];
}
g[0][u] = 1;
for (int i = k; i >= 0; i--) {
for (int j : {k - i, k - i - 1}) {
if (j < 0) continue;
i64 a = min(g[i][u], f[j][u]);
g[i][u] -= a, f[j][u] -= a;
}
if (i == k && g[k][u] > 0) {
i64 a = (g[k][u] + s - 1) / s;
ans += a, f[0][u] += a * s - g[k][u], g[k][u] = 0;
}
}
}
void _main() {
cin >> n >> s >> k;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
dfs(1, -1);
for (int i = k; i >= 0; i--) {
for (int j = k - i; j >= 0; j--) {
i64 a = min(g[i][1], f[j][1]);
g[i][1] -= a, f[j][1] -= a;
}
}
i64 rem = 0;
for (int i = 0; i <= k; i++) rem += g[i][1];
cout << ans + (rem + s - 1) / s;
}
:::::
P4785 [BalticOI 2016] 交换 (Day2)
给出一个长为
n 的排列a_i 。有n-1 轮操作,第k 次操作可以交换a_k 和a_{\lfloor k/2\rfloor} 。你需要最小化最终排列的字典序并输出。
:::::success[题解] 思维自然且很有启发性的好题,点赞!
题目中
对原排列建立完全二叉树,根节点为
我们按前序遍历的顺序依次考虑每个节点
- 若
x 是最小值,不做交换,左右子树分别递归求解; - 若
y 是最小值,交换x \to y ,然后左右子树递归求解; - 若
z 是最小值,交换x \to z 或者依次交换x \to y, y \to z 都可行。左右子树有x,y 和y,x 两种可能。
这里需要说明一下,直接将较小值作为左子树根是错误的,因为较小值可能在左子树中被替换。
我们将一个值沉入一棵子树,其必然经历若干次替换后停止在某个位置。这个位置可以通过模拟上述流程算出。
设
对于
| 我们注意到 |
|---|
:::::info[代码]
const int N = 2e5 + 5;
int n, a[N], ans[N];
umap<int, int> mem[N];
int f(int u, int val) {
int ls = u << 1, rs = u << 1 | 1;
if (ls > n) return u;
if (rs > n) return val < a[ls] ? u : f(ls, val);
if (mem[u].find(val) != mem[u].end()) return mem[u][val];
int m = min({val, a[ls], a[rs]});
if (m == val) return mem[u][val] = u;
if (m == a[ls]) return mem[u][val] = f(ls, val);
if (val < a[ls]) return mem[u][val] = min(f(ls, val), f(rs, val));
return mem[u][val] = f(ls, a[ls]) < f(rs, a[ls]) ? f(rs, val) : f(ls, val);
}
void solve(int u, int val) {
int ls = u << 1, rs = u << 1 | 1;
if (ls > n) return ans[u] = val, void();
if (rs > n) {
int v = a[ls];
if (v < val) swap(v, val);
return ans[u] = val, solve(ls, v), void();
}
int m = min({val, a[ls], a[rs]});
if (m == val) {
ans[u] = val, solve(ls, a[ls]), solve(rs, a[rs]);
} else if (m == a[ls]) {
ans[u] = a[ls], solve(ls, val), solve(rs, a[rs]);
} else {
ans[u] = a[rs];
int x = val, y = a[ls];
if (x > y) swap(x, y);
if (f(ls, x) < f(rs, x)) solve(ls, x), solve(rs, y);
else solve(ls, y), solve(rs, x);
}
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = 1e9, solve(1, a[1]);
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
:::::
P5311 [Ynoi2011] 成都七中
给你一个
n 个节点的无根树,点有颜色,q 次查询给出l,r, x ,求保留[l,r] 中的节点后x 所在连通块颜色数。
:::::success[题解]
记
点分治起手,设分治中心为
现在问题转化为:求从
设
于是从
将颜色去重后进行二维数点。对于同种颜色,若存在两点
采用类似于 HH 的项链的处理方式,维护一个树状数组,同时记录每种颜色上一次出现的位置,激活新位置时要删除上一个位置。
按照上述过程实现,视
::::::
:::::info[代码]
const int N = 1e5 + 5;
using query = tuple<int, int, int, int>; // {l, r, x, id}
using point = tuple<int, int, int>; // {x, y, col}
struct BIT {
int tr[N];
void add(int x, int c) {
for (; x < N; x += lowbit(x)) tr[x] += c;
}
int ask(int x) {
int res = 0;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
} B;
int n, q, col[N], ans[N];
vector<int> e[N];
int ctr, cur, sz[N], vis[N];
void dfs1(int u, int fa) {
sz[u] = 1;
for (int v : e[u]) {
if (v == fa || vis[v]) continue;
dfs1(v, u), sz[u] += sz[v];
}
if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) {
cur++;
for (int v : e[u]) if (v != fa && !vis[v]) dfs2(v, u);
}
int mn[N], mx[N], bel[N];
void dfs3(int u, int fa, int minv, int maxv, int b, vector<int>& vec) {
minv = min(minv, u), maxv = max(maxv, u);
mn[u] = minv, mx[u] = maxv, bel[u] = b, vec.emplace_back(u);
for (int v : e[u]) if (v != fa && !vis[v]) dfs3(v, u, minv, maxv, b, vec);
}
int last[N];
vector<query> child[N];
vector<pair<int, int>> cp[N];
void update(int u, vector<query>& q, vector<pair<int, vector<query>>>& nxt) {
vector<int> vec = {u};
mn[u] = u, mx[u] = u, bel[u] = -1;
for (int v : e[u]) {
if (!vis[v]) dfs3(v, u, u, u, v, vec);
}
vector<query> now;
for (auto& [l, r, x, id] : q) {
if (l <= mn[x] && mx[x] <= r) now.emplace_back(l, r, x, id);
else child[bel[x]].emplace_back(l, r, x, id);
}
for (int v : e[u]) { // 下传询问
if (vis[v] || child[v].empty()) continue;
nxt.emplace_back(v, child[v]), child[v].clear();
}
// 扫描线
vector<point> p;
for (int v : vec) cp[col[v]].emplace_back(mn[v], mx[v]);
for (int v : vec) { // 去重
if (cp[col[v]].empty()) continue;
sort(cp[col[v]].begin(), cp[col[v]].end(), greater<pair<int, int>>());
int ymin = 1e9;
for (auto& [x, y] : cp[col[v]]) {
if (y < ymin) ymin = y, p.emplace_back(x, y, col[v]);
}
cp[col[v]].clear();
}
sort(now.begin(), now.end(), greater<query>());
sort(p.begin(), p.end(), greater<point>());
int i = 0;
vector<int> undo;
for (auto& [l, r, x, id] : now) {
for (; i < (int)p.size() && get<0>(p[i]) >= l; i++) {
auto& [_, y, c] = p[i];
if (last[c]) B.add(last[c], -1);
last[c] = y, B.add(last[c], 1);
undo.emplace_back(c);
}
ans[id] = B.ask(r);
}
for (int c : undo) if (last[c]) B.add(last[c], -1), last[c] = 0;
}
void solve(int u, vector<query>& q) {
if (q.empty()) return;
vis[u] = true;
vector<pair<int, vector<query>>> nxt;
update(u, q, nxt);
for (auto& [v, vec] : nxt) {
cur = ctr = 0, dfs2(v, u), dfs1(v, u);
solve(ctr, vec);
}
}
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> col[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
vector<query> vec;
for (int i = 1, l, r, x; i <= q; i++) {
cin >> l >> r >> x;
vec.emplace_back(l, r, x, i);
}
cur = n, dfs1(1, -1), solve(ctr, vec);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::