谁家刚学会一个知识点就放黑来做啊。
长链剖分
建议在会重链剖分的基础上再来学长链剖分。
长链剖分与重链剖分不同的地方在于：重剖以子树大小来选重儿子，长剖以子树深度来选重儿子。
长剖的优势有： 可以 \(\mathcal{O}(1)\) 求 \(k\) 级祖先，可以在与深度有关的树形 dp 中优化掉一维。
长剖的劣势有：求 LCA 是 \(\mathcal{O}(\sqrt{n})\) 的（其实用二分 + \(k\) 级祖先就好）。
代码就从重剖那里改改就好。
长链剖分优化 dp
CF1009F Dominant Indices
先来一道例题：CF1009F。
题意：
给定一棵以 \(1\) 为根，\(n\) 个节点的树。设 \(d(u,x)\) 为 \(u\) 子树中到 \(u\) 距离为 \(x\) 的节点数。
对于每个点，求一个最小的 \(k\)，使得 \(d(u,k)\) 最大。
有一个很明显的“dp”：令 \(dp_{i, j}\) 表示以 \(i\) 为根的子树内深度为 \(j\) 的结点个数。
转移方程：\(dp_{u, i} = \sum\limits_{v \in son_{u}}dp_{v, i - 1}(i \geqslant 1)\)，\(dp_{u, 0} = 1\)。
（这里就是一个简单的统计所以连 dp 都算不上。）
但是这么做是 \(\mathcal{O}(n^2)\) 的，怎么优化呢？
用一种类似 dsu on tree 的思想，先计算某个子树的 dp，再用一种特殊的方法快速转移（因为第一个被计算的子树一般都有特殊转移方法），再暴力合并其它子树。
而这个时候我们如果选择深度最大的那棵子树先合并，那么就可以将时间复杂度的次数将为 \(1\)！
为什么呢？因为在每个结点的第一次转移中，有：\(dp_{u, i} = dp_{v, i - 1}\)，我们完全可以把相同的那一部分给两个结点共用，多出来的一个点也就是 \(dp_{u, 0}\) 设为 \(0\) 就好。
而其它的结点，每条链仅仅会在链顶的时候被暴力合并，而合并的复杂度是 \(\mathcal{O}(len)\)（\(len\) 为链长），均摊下来就是 \(\mathcal{O}(n)\)。
有点小抽象，而且这个复杂度降得也给我整得不明不白的，但这么分析下来它就是降了。
放一份代码：
#include <bits/stdc++.h>
using namespace std;
int n, u, v, son[1000005], len[1000005], ans[1000005], *dp[1000005];
vector<int> g[1000005];
void dfs1(int now, int father) {
for(const auto& i : g[now]) {
if(i != father) {
dfs1(i, now);
if(len[i] > len[son[now]]) son[now] = i;
}
}
len[now] = len[son[now]] + 1;
}
void dfs2(int now, int father) {
if(now != son[father]) dp[now] = new int[len[now]];
else dp[now] = dp[father] + 1;
dp[now][0] = 1;
if(son[now]) {
dfs2(son[now], now);
ans[now] = ans[son[now]] + 1;
}
for(const auto& i : g[now]) {
if(i != father && i != son[now]) {
dfs2(i, now);
for(int j = 0; j < len[i]; ++j) {
dp[now][j + 1] += dp[i][j];
if(dp[now][j + 1] > dp[now][ans[now]] || (dp[now][j + 1] == dp[now][ans[now]] && j + 1 < ans[now])) {
ans[now] = j + 1;
}
}
}
}
if(dp[now][ans[now]] == 1) ans[now] = 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 2; i <= n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1, 1);
dfs2(1, 1);
for(int i = 1; i <= n; ++i) cout << ans[i] << '\n';
return 0;
}
WC2010 重建计划
首先平均数的部分用 01 分数规划的思想用二分把它转化成检查 \(\sum v_{i} \geqslant 0\)。
也就是说我们要在树上找到一条链使得这条链的权值和非负。
如何统计链？当然是在两端的 LCA 处统计，所以我们只要知道一个点连下去的链的最大权值和即可。
令 \(dp_{i, j}\) 表示以 \(i\) 为链顶，长度为 \(j\) 的链的最大权值和，转移有：
\[dp_{u, i} = \max\limits_{v \in son_{u}}\left\{dp_{v, i - 1} + w(u, v)\right\} \]类似例题，先特殊转移长链剖分出来的重儿子，有 \(dp_{u, i} = dp_{v, i - 1} + w(u, v)\)。
如何判断是否存在一条链的权值和非负？在转移的时候以及转移结束后判断即可。
具体地，枚举暴力转移的链的长度的时候（假设长度为 \(len\)），在已经转移好的部分中查询是否有一条长度在 \([\max(L - len, 0), U - len]\) 的链与其的权值和非负。
也就是说我们需要实现「区间加」，「单点修」，「区间查询 \(\max\)」，「单点查询」这几个功能，用一棵线段树即可。
其实如果模板题会了的话这道题还是很简单的。
代码：
#include <bits/stdc++.h>
using namespace std;
constexpr double eps = 1e-4;
int n, lower, upper, u, v, w, cnt, son[100005], val[100005], len[100005], lt[100005], rt[100005];
double sub, bl, br, mid, ans;
vector< pair<int, int> > g[100005];
bool flag;
struct Segment_Tree {
int l[400005], r[400005];
double mx[400005], tag[400005];
#define lc (k << 1)
#define rc (lc | 1)
#define mid ((l[k] + r[k]) >> 1)
void build(int k) {
mx[k] = -1e15, tag[k] = 0;
if(l[k] == r[k]) return;
l[lc] = l[k], r[lc] = mid, l[rc] = mid + 1, r[rc] = r[k];
build(lc), build(rc);
}
void push_down(int k) {
mx[lc] += tag[k], mx[rc] += tag[k];
tag[lc] += tag[k], tag[rc] += tag[k];
tag[k] = 0;
}
void push_up(int k) {
mx[k] = max(mx[lc], mx[rc]);
}
void change_add(int k, const int& L, const int& R, const double& v) {
if(L <= l[k] && r[k] <= R) {
tag[k] += v;
mx[k] += v;
return;
}
push_down(k);
if(L <= mid) change_add(lc, L, R, v);
if(R > mid) change_add(rc, L, R, v);
push_up(k);
}
void change_max(int k, const int& pos, const double& v) {
if(l[k] == r[k]) {
mx[k] = max(mx[k], v);
return;
}
push_down(k);
if(pos <= mid) change_max(lc, pos, v);
else change_max(rc, pos, v);
push_up(k);
}
double ask(int k, const int& L, const int& R) {
if(L > R) return -1e15;
if(L <= l[k] && r[k] <= R) return mx[k];
double ret = -1e15;
push_down(k);
if(L <= mid) ret = max(ret, ask(lc, L, R));
if(R > mid) ret = max(ret, ask(rc, L, R));
push_up(k);
return ret;
}
#undef mid
} tree;
void dfs1(int now, int father) {
for(const auto& i : g[now]) {
if(i.first != father) {
dfs1(i.first, now);
if(len[i.first] > len[son[now]]) son[now] = i.first;
}
}
len[now] = len[son[now]] + 1;
}
void dfs2(int now, int father) {
if(now != son[father]) {
lt[now] = cnt;
rt[now] = cnt + len[now] - 1;
cnt += len[now];
}
else lt[now] = lt[father] + 1, rt[now] = rt[father];
for(const auto& i : g[now]) {
if(i.first != father) {
if(i.first == son[now]) val[now] = i.second;
dfs2(i.first, now);
}
}
}
void dfs3(int now, int father) {
if(son[now]) {
dfs3(son[now], now);
tree.change_add(1, lt[now] + 1, rt[now], val[now] - sub);
}
tree.change_max(1, lt[now], 0.0);
for(const auto& i : g[now]) {
if(i.first != father && i.first != son[now]) {
dfs3(i.first, now);
for(int j = 0; j < len[i.first]; ++j) {
auto dp = tree.ask(1, lt[i.first] + j, lt[i.first] + j) + i.second - sub;
if(tree.ask(1, lt[now] + max(lower - j - 1, 0), min(lt[now] + upper - j - 1, rt[now])) + dp >= 0.0) {
flag = true;
}
}
for(int j = 0; j < len[i.first]; ++j) {
auto dp = tree.ask(1, lt[i.first] + j, lt[i.first] + j) + i.second - sub;
tree.change_max(1, lt[now] + j + 1, dp);
}
}
}
if(tree.ask(1, lt[now] + lower, min(lt[now] + upper, rt[now])) >= 0.0) flag = true;
}
bool check(double c) {
sub = c, flag = false;
tree.build(1);
dfs3(1, 1);
return flag;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> lower >> upper;
for(int i = 2; i <= n; ++i) {
cin >> u >> v >> w;
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
dfs1(1, 1);
cnt = 1;
dfs2(1, 1);
tree.l[1] = 1, tree.r[1] = n;
check(2.5);
bl = 1.0, br = 1000000.0;
while(br - bl > eps) mid = (bl + br) / 2.0, check(mid) ? (ans = mid, bl = mid + eps) : (br = mid - eps);
cout << fixed << setprecision(3) << ans;
return 0;
}