CF671D Roads in Yusland

题目大意

题目链接

给定一棵 (n) 个节点的、以 (1) 为根的有根树。

有 (m) 条路径 ((u_i, v_i))，保证 (v_i) 是 (u_i) 的祖先（祖先包括这个点自己）。每条路径有一个价格。

请选择若干条路径，将树上所有边覆盖（一条边可以被多次覆盖）。求所选路径价格之和的最小值。

数据范围：(1leq n,mleq 3 imes 10^5)。

本题题解

定义根节点的深度为 (1)，其他每个点的深度是它父亲的深度 (+1)。记点 (u) 的深度为 ( ext{dep}(u))。

对于给出的路径 ((u_i, v_i))（(v_i) 是 (u_i) 的祖先），我们在节点 (u_i) 处考虑是否选择它。以下称 (u_i) 为“起点”，(v_i) 为“终点”。

朴素的树形 DP。设 ( ext{dp}(u,j)) 表示选择了若干条起点在 (u) 的子树内的路径，使得这些路径覆盖了 (u) 子树内的所有边，并且它们的终点的深度的最小值为 (j)（(jleq ext{dep}(u))），达到这种情况所需的最小花费。感性理解，就是所选路径，在 (u) 的子树外，最远覆盖到深度为 (j) 的祖先。

同时设 (f(u) = min_{j = 1}^{ ext{dep}(u) - 1} ext{dp}(u, j))，也就是至少覆盖到 (u) 和父亲之间的边，所需的花费。

转移。先不考虑以 (u) 为起点的路径，则有：

[ ext{dp}(u, j) = min_{vin ext{son}(u)}left{ ext{dp}(v, j) + sum_{win ext{son}(u), w eq v}f(w) ight} ]

也就是枚举一个儿子 (v)，让它里面的路径，最小深度达到了 (j)。然后其他儿子 (w) 就可以随便选了。细心的读者或许发现，(f(w)) 中可能包含，覆盖到的最小深度比 (j) 更小的情况，但这显然是不影响答案的。

上述转移要枚举 (v) 和 (w)，是一个双重循环，比较丑。把它改写一下：

[ ext{dp}(u, j) = sum_{v in ext{son}(u)} f(v) + min_{vin ext{son}(u)}{ ext{dp}(v,j) - f(v)} ]

接下来考虑以 (u) 为起点的路径，设终点的深度为 (j)，价格为 (c)，则转移也是类似的：

[ ext{dp}(u,j) = sum_{v in ext{son}(u)} f(v) + c ]

答案就是 ( ext{dp}(1, 1))。这个朴素 DP 的时间复杂度为 (mathcal{O}(n^2))。

考虑优化。容易想到，用线段树来维护 DP 的第二维。需要支持：

区间加：转移前把所有 ( ext{dp}(v,j)) 加上 (-f(v))；以及最后把所有 ( ext{dp}(u,j)) 加上 (sum_{v in ext{son}(u)} f(v))。
查询区间最小值：也就是求出 (f(v))。
线段树合并。合并时，对应位置取 (min)。发现这相当于要支持区间取 (min)。
单点对一个数取 (min)：在考虑以 (u) 为起点的路径时，单点对 (c) 取 (min)。发现这已经被上一条（区间取 (min)）包含。

可以用线段树维护两个懒标记：区间加法，和区间对一个数取 (min)，同时记录区间最小值。就能支持上述的操作了。关于双标记的顺序问题：下放懒标记时，先下放区间加法，再下放区间取 (min)。做区间加时，要同时更新区间取 (min) 的懒标记。

时间、空间复杂度 (mathcal{O}((n + m) log n))。因为本题空间限制较小，难以通过。

继续优化。考虑对每个点，维护一个 ( exttt{std::set})。里面存二元组：((j, ext{dp}(v, j)))。以 (j) 为关键字排序。这个 ( exttt{set}) 里，其实就是原来的 DP 数组中所有不为 (infty) 的元素。

考虑转移时的操作。

区间加法。发现只要我们把 (j > ext{dep}(u)) 的元素及时弹出，区间加就变为了全局加。因此只要维护一个全局的标记即可。
合并可以采用启发式合并。也就是把小的一个一个“插入”到大的里面。
单点取 (min) 也相当于“插入”一个新元素。

注意，这里的“插入”不是直接插入，如果 ( exttt{set}) 里已经存在相同的 (j)，则需要把第二元拿出来比大小。最终每个 (j) 只会在 ( exttt{set}) 里出现一次。

最后一个问题是查询最小值（和区间加类似，在支持弹出后，区间最小值查询就变成了全局最小值查询）。因为我们的二元组，在 ( exttt{set}) 里是按第一元 (j) 排序的，故难以同时维护出第二元的最小值。数据结构的能力已经用到极限了，我们就必须回过头来继续挖掘题目的性质。发现对于 (j_1 < j_2)，若 ( ext{dp}(u, j_1) < ext{dp}(u, j_2))，则 ( ext{dp}(u, j_2)) 不会对答案有任何贡献。换句话说，此时我们把 ( ext{dp}(u, j_2)) 视为 (infty)，也不会影响答案。因此可以直接把 ( ext{dp}(u, j_2)) 从 ( exttt{set}) 里删掉。于是这样维护出的 ( exttt{set})，所有元素第二元一定单调递减。直接取最后一个元素，就是第二元最小的。

时间复杂度 (mathcal{O}((n + m)log^2 n))，空间复杂度 (mathcal{O}(n + m))。可以通过本题。

参考代码

实际提交时建议使用读入优化，详见本博客公告。

// problem: CF671D
#include <bits/stdc++.h>
using namespace std;

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 3e5;
const ll LL_INF = 1e18;

int n, m;

struct EDGE { int nxt, to; } edge[MAXN * 2 + 5];
int head[MAXN + 5], tot;
inline void add_edge(int u, int v) { edge[++tot].nxt = head[u]; edge[tot].to = v; head[u] = tot; }

vector<pii> plan[MAXN + 5];

int dep[MAXN + 5];

int id[MAXN + 5];
set<pair<int, ll> > dps[MAXN + 5];
ll tag_add[MAXN + 5];

void ins(int u, int p, ll val) {
	set<pair<int, ll> > :: iterator it = dps[id[u]].lower_bound(make_pair(p, -LL_INF));
	if (it != dps[id[u]].end() && (it -> fi) == p) {
		if ((it -> se) + tag_add[id[u]] > val) {
			dps[id[u]].erase(it);
			dps[id[u]].insert(make_pair(p, val - tag_add[id[u]]));
		}
	} else {
		if (it != dps[id[u]].begin() && ((--it) -> se) + tag_add[id[u]] <= val) {
			return;
		}
		dps[id[u]].insert(make_pair(p, val - tag_add[id[u]]));
	}
	
	set<pair<int, ll> > :: iterator st = dps[id[u]].lower_bound(make_pair(p + 1, -LL_INF));
	set<pair<int, ll> > :: iterator ed = st;
	while (ed != dps[id[u]].end() && (ed -> se) + tag_add[id[u]] >= val)
		++ed;
	if (ed != it)
		dps[id[u]].erase(st, ed); // 维持单调性
}
void del(int u, int lim) {
	while (SZ(dps[id[u]])) {
		set<pair<int, ll> > :: iterator it = dps[id[u]].end();
		--it;
		if ((it -> fi) <= lim)
			break;
		dps[id[u]].erase(it);
	}
}
ll get_min(int u) {
	assert(SZ(dps[id[u]]) > 0);
	return (dps[id[u]].rbegin() -> se) + tag_add[id[u]];
}

void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	
	for (int i = 0; i < SZ(plan[u]); ++i) {
		int v = plan[u][i].fi;
		int c = plan[u][i].se;
		
		ins(u, dep[v], c);
	}
	ins(u, dep[u], 0);
	
	ll sum = 0;
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if (v == fa)
			continue;
		dfs(v, u);
		
		del(v, dep[u]);
		if (!SZ(dps[id[v]])) {
			cout << -1 << endl;
			exit(0);
		}
		
		ll f = get_min(v);
		sum += f;
		tag_add[id[v]] -= f;
		
		if (SZ(dps[id[u]]) < SZ(dps[id[v]]))
			swap(id[u], id[v]);
		
		for (set<pair<int, ll> > :: iterator it = dps[id[v]].begin();
		it != dps[id[v]].end(); ++it) {
			ins(u, it -> fi, (it -> se) + tag_add[id[v]]);
		}
		dps[id[v]].clear();
	}
	
	tag_add[id[u]] += sum;
	
//	cerr << "************ " << u << endl;
//	for (set<pair<int, ll> > :: iterator it = dps[id[u]].begin();
//	it != dps[id[u]].end(); ++it) {
//		cerr << (it -> fi) << " " << (it -> se) + tag_add[id[u]] << endl;
//	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		add_edge(u, v);
		add_edge(v, u);
	}
	for (int i = 1; i <= m; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		if (u != v) {
			plan[u].push_back(mk(v, c));
		}
	}
	
	for (int i = 1; i <= n; ++i)
		id[i] = i;
	dfs(1, 1);
	
	del(1, 1);
	ll ans = get_min(1);
	cout << ans << endl;
	return 0;
}