P2495 [SDOI2011] 消耗战 线段树合并做法
看到题解里面有一个线段树合并做法！感觉很厉害，但是题解和代码都不是很详细所以补充一下
不妨假设 \(dp_u\) 表示 \(u\) 及其子树内把所有关键点都切断的最小代价，那么不难有
\[\begin{equation}
dp_u =
\begin{cases}
+\infty &u是关键点\\
\sum_{v\in \operatorname{son}(u)}\min(dp_v, w_i) &u不是关键点
\end{cases}
\nonumber
\end{equation}
\]
其中 \(w_i\) 是点 \(u\) 与点 \(v\) 之间连的边权
因为每个 \(dp\) 值只会转移到一个数，可以直接滚掉，考虑 \(m\) 个询问一起做，
在 \(v\) 转移到 \(u\) 的时候先对 \(v\) 中所有 \(dp\) 值与 \(w_i\) 取一个 \(\min\)，然后把 \(u\) 的对应位置的 \(dp\) 值加上 \(v\) 对应位置的 \(dp\) 值即可
也就是先
\[\forall k\in [1, m],dp_{v,k} \leftarrow \min(dp_{v,k}, w_i)\\
\]
再
\[\forall k\in [1, m],dp_{u,k} \leftarrow dp_{u,k}+dp_{v,k}
\]
这两个操作实际上可以线段树合并维护，对于操作 \(1\)，全局打一个取 \(\min\) 的 \(tag\)，随后对于操作 \(2\)，把 \(u\) 和 \(v\) 对应的树合并，并在叶子处把对应位置相加即可，最后把所有叶子按顺序输出
非常好写，并且比虚树短了不知道多少
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int h[N], e[N << 1], ne[N << 1], idx;
ll w[N << 1];
int rt[N];
vector<int> q[N];
int n, m, tot;
inline void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
struct node {
int ls, rs;
ll v;
}tr[N << 4];
inline void chkmin(ll &x, ll y) {if(x > y) x = y;}
inline void chkmax(ll &x, ll y) {if(x < y) x = y;}
void insert(int &u, int l, int r, int pos, ll x) {
if(!u)
u = ++tot, tr[u].v = x;
if(l == r) {
tr[u].v = x;
return ;
}
int mid = l + r >> 1;
if(pos <= mid)
insert(tr[u].ls, l, mid, pos, x);
else
insert(tr[u].rs, mid + 1, r, pos, x);
}
inline void pushdown(int u) {
chkmin(tr[tr[u].ls].v, tr[u].v);
chkmin(tr[tr[u].rs].v, tr[u].v);
tr[u].v = inf;
}
int merge(int u, int v, int l, int r) {
if(!u || !v)
return u | v;
if(l == r) {
tr[u].v += tr[v].v;
return u;
}
int mid = l + r >> 1;
pushdown(u), pushdown(v);
tr[u].ls = merge(tr[u].ls, tr[v].ls, l, mid);
tr[u].rs = merge(tr[u].rs, tr[v].rs, mid + 1, r);
return u;
}
void dfs(int u, int fa) {
//把这若干个位置的 dp 值设为 inf
for(auto query : q[u])
insert(rt[u], 1, m, query, inf);
for(int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if(v == fa)
continue;
dfs(v, u);
chkmin(tr[rt[v]].v, w[i]);
rt[u] = merge(rt[u], rt[v], 1, m);
}
}
void print(int u, int l, int r) {
if(!u)
return ;
if(l == r) {
printf("%lld\n", tr[u].v);
}
int mid = l + r >> 1;
pushdown(u);
print(tr[u].ls, l, mid);
print(tr[u].rs, mid + 1, r);
}
int main() {
memset(h, -1, sizeof(h));
scanf("%d", &n);
for(int i = 2; i <= n; i++) {
int a, b;
ll c;
scanf("%d%d%lld", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
scanf("%d", &m);
for(int i = 1; i <= m; i++) {
int p;
scanf("%d", &p);
for(int j = 1; j <= p; j++) {
int u;
scanf("%d", &u);
q[u].push_back(i);
}
}
dfs(1, 0);
print(rt[1], 1, m);
return 0;
}