题解 CF671D 【Roads in Yusland】
xht
2020-03-01 01:04:15
> [CF671D Roads in Yusland](https://codeforces.com/contest/671/problem/D)
## 题意
- 给定一棵 $n$ 个点的以 $1$ 为根的树。
- 有 $m$ 条路径 $(x,y)$，保证 $y$ 是 $x$ 的祖先，每条路径有一个权值。
- 你要在这些路径中选择若干条路径，使它们能覆盖每条边，同时权值和最小。
- $n,m \le 3 \times 10^5$。
## 题解
设 $f_i$ 表示**覆盖 $i$ 子树内的所有边和 $i$ 与其父亲的边**的最小权值，则答案就是 $\sum_{x \in \operatorname{son}(1)} f_x$。
然而并不是所有 $f$ 都是最优的，对于一种**覆盖 $i$ 子树内的所有边和 $i$ 与其父亲的边**的方案，可能它并不是最小权值，但是它向上延伸得更长。
因此我们要保留住所有可能最优的方案，同时要计算其中的最小值，这启发我们考虑小根堆。具体来说，对于节点 $i$，$i$ 上的小根堆内存储了**覆盖 $i$ 子树内的所有边和 $i$ 与其父亲的边**的所有可能最优的方案。
考虑如何转移，即当 $x \in \operatorname{son}(y)$ 时，如何将 $x$ 上的方案转移到 $y$ 上。对于一个权值为 $k$ 的方案：
- 如果向上延伸超过了 $y$，则这种方案在 $y$ 的小根堆里权值应该为 $k + \sum_{z \in \operatorname{son}(y)} f_z - f_x$。
- 如果正好向上延伸到 $y$，则这种方案不应该出现在 $y$ 上，需要被扔掉。
这时候我们发现，一个点有来自多个儿子的小根堆，显然我们需要将它们合并起来，于是将小根堆改为左偏树即可。
同时，我们还需要支持整棵左偏树加上一个定值，打个标记即可。
对于需要扔掉的方案，由于我们不需要实时删除，因此考虑我们暂时先保留它们，当它们成为根时再弹出即可。
设 $n,m$ 同阶，总时间复杂度为 $\mathcal O(n \log n)$。
## 代码
```cpp
#define Fail print(-1), exit(0)
const int N = 3e5 + 7;
int n, m, d[N], tot, rt[N];
ll f[N], ans;
vi e[N];
vector<pi> p[N];
struct T {
pair<ll, int> x;
ll z;
int l, r, f, d;
} t[N];
inline void add(int x, ll k) {
if (x) t[x].x.fi += k, t[x].z += k;
}
inline void spd(int x) {
if (t[x].z) add(t[x].l, t[x].z), add(t[x].r, t[x].z), t[x].z = 0;
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (t[x].x > t[y].x) swap(x, y);
spd(x);
t[t[x].r=merge(t[x].r,y)].f = x;
if (t[t[x].r].d > t[t[x].l].d) swap(t[x].l, t[x].r);
t[x].d = t[t[x].r].d + 1;
return x;
}
void dfs(int x, int fa) {
d[x] = d[fa] + 1;
for (pi o : p[x])
t[++tot].x = o, t[tot].d = 1, rt[x] = merge(rt[x], tot);
ll s = 0;
for (int y : e[x])
if (y != fa) {
dfs(y, x), s += f[y];
add(rt[y], -f[y]), rt[x] = merge(rt[x], rt[y]);
}
add(rt[x], s);
while (rt[x] && d[t[rt[x]].x.se] >= d[x])
spd(rt[x]), rt[x] = merge(t[rt[x]].l, t[rt[x]].r);
if (!rt[x]) Fail;
f[x] = t[rt[x]].x.fi;
}
int main() {
rd(n), rd(m);
for (int i = 1, x, y; i < n; i++)
rd(x), rd(y), e[x].pb(y), e[y].pb(x);
for (int i = 1, x, y, z; i <= m; i++)
rd(x), rd(y), rd(z), p[x].pb(mp(z, y));
d[1] = 1;
for (int x : e[1]) dfs(x, 1), ans += f[x];
print(ans);
return 0;
}
```