CF671D Roads in Yusland 题解

CF671D Roads in Yusland

题意

• 给定一棵 $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)$。

代码

#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;
}