题解 accoders::NOI 5511【漂亮轰炸（bomb）】
http://47.92.197.167:5283/contest/406/problem/4
BZOJ3252 是弱化版。
problem
一棵树，边带权。\(Q\) 次询问，给定 \(k\) 和一个首都点，选择 \(k\) 条路径轰炸，其中必须由一轮要轰炸首都，但没有要求每条路径都经过首都。每条边只能被炸一次，贡献值算一次，求被炸到的边的总和的最大值。\(n,Q\leq 500000\)。
solution
- 选出的路径必须有一条的一端是直径端点。否则我可以换。
- 选出的路径两端必须是叶子，将路径扩展的叶子不定不会更劣。
考虑随便跳出一条直径，以直径两端分别为根跑两次。以下考虑其中一个。
我们怎么求答案呢？
- 选出一个叶子和根连起来，选出其他 \(2(k-1)\) 个叶子，按照某种 dfn 序交错的方法可以选出这 \(2k-1\) 个叶子和根组成的虚树上的所有边权。
- 通过其他方式使得这个虚树经过首都。
考虑对树做长链剖分。意思是定义了 \(hei_i\) 表示点 \(i\) 往下到最深的叶子的距离（带权），然后区分出长儿子和轻儿子，有了长链剖分。
这样的长链剖分有性质：
- 对于点 \(u\)，点 \(u\) 所在长链权值（记为 \(sum_u\)，算上链顶的轻边）$\geq $ 它的任意一个轻儿子的所在长链权值。否则他不叫轻儿子。
- 考虑如果我们将所有长链排序后选出前 \(2k-1\) 大的链，则这些 链 接一起 一定连通了，然后可以通过神秘 dfn 序成功构造方案。
所以我们现在有了一个方案。需要调整之。
如果选到了首都，那么这个方案最优了。
否则考虑换掉一条链。考虑如果换掉 \(y\)：
-
如果 \(y\) 的链顶不是首都 \(x\) 的祖先，它们互不影响，去掉 \(y\) 整条链，接上 \(x\)。我们可以选最短的链换掉，断言不可能有依赖。
-
如果 \(y\) 的链顶是首都 \(x\) 的祖先，则去掉 \(lca(x, y)\to y\) 这一段，加上 \(x\to lca(x, y)\)。
-
注意我们默认 \(lca(x, y)\) 子树内只有 \(y\) 一条链，因为如果有多条链，会以第一种 \(y\) 被枚举到，或者第一种 \(y\) 更优。
考虑 \(lca(x, y)\) 我们取 \(x\) 向上跳祖先跳到的第一个有链被选的地方，记为 \(p\)，然后换掉 \(p\) 下面的一条链即可。
\(O((n+Q)\log n)\)。
code
#include <cstdio>
#include <vector>
#include <tuple>
#include <utility>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int n, Q;
vector<pair<int, int>> g[1 << 19];
struct Tree {
int root, son[1 << 19], bty[1 << 19], rnk[1 << 19], cnt;
LL hei[1 << 19], dep[1 << 19], sum[1 << 19];
int fa[20][1 << 19], *ft = fa[0], H[1 << 19];
vector<pair<LL, int>> ycs;
void dfs(int u, int F) {
ft[u] = F;
bty[u] = u;
rnk[++cnt] = u;
for (auto &&edge: g[u]) {
int v, w; tie(v, w) = edge;
if (v == F) continue;
dep[v] = dep[u] + w;
dfs(v, u);
if (hei[u] < hei[v] + w) {
hei[u] = hei[v] + w;
son[u] = v;
bty[u] = bty[v];
}
}
for (auto &&edge: g[u]) {
int v, w; tie(v, w) = edge;
if (v == F) continue;
if (son[u] != v) ycs.emplace_back(hei[v] + w, bty[v]);
}
}
void build(int rt) {
debug("choose root = %d\n", rt);
dfs(root = rt, 0);
ycs.emplace_back(hei[rt], bty[rt]);
//sort(ycs.begin(), ycs.end(), greater<pair<LL, int>>());
sort(ycs.begin(), ycs.end(), greater<pair<int, int>>());
for (auto e: ycs) debug("{%lld [%d]}, ", e.first, e.second);
debug("\n");
sum[0] = ycs[0].first;
for (int i = 1; i < ycs.size(); i++) sum[i] = sum[i - 1] + ycs[i].first;
memset(H, 0x3f, sizeof H);
for (int i = 0; i < ycs.size(); i++) H[ycs[i].second] = i;
for (int i = n; i >= 1; i--) {
int u = rnk[i];
H[ft[u]] = min(H[ft[u]], H[u]);
}
for (int j = 1; j <= 19; j++) {
for (int u = 1; u <= n; u++)
fa[j][u] = fa[j - 1][fa[j - 1][u]];
}
}
LL query(int u, int k) {
if (k >= ycs.size()) return sum[ycs.size() - 1];
if (H[u] < k) return sum[k - 1];
LL now = sum[k - 1], c = dep[bty[u]];
int p = u;
for (int j = 19; j >= 0; j--) if (H[fa[j][p]] >= k) p = fa[j][p];
p = ft[p], assert(p && H[p] < k);
c -= dep[p];
return max(now - hei[p] + c, now - ycs[k - 1].first + c);
}
};
Tree T1, T2;
int bfs(int s) {
queue<int> q;
static LL dis[1 << 19];
memset(dis, 0x3f, sizeof dis);
int last = s;
for (q.push(s), dis[s] = 0; !q.empty(); ) {
int u = q.front(); q.pop();
if (dis[u] > dis[last]) last = u;
for (auto &&edge: g[u]) {
int v, w; tie(v, w) = edge;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(v);
}
}
}
return last;
}
int main() {
#ifndef Robin
freopen("bomb.in", "r", stdin);
freopen("bomb.out", "w", stdout);
#endif
scanf("%d%d", &n, &Q);
for (int i = 1, u, v, w; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
int p = bfs(1);
T1.build(p), T2.build(bfs(p));
for (int i = 1, u, k; i <= Q; i++) {
scanf("%d%d", &u, &k);
k = 2 * k - 1;
printf("%lld\n", max(T1.query(u, k), T2.query(u, k)));
}
return 0;
}