CF671D Roads in Yusland

第一想法：设 \(f_{u,k}\) 表示处理完 \(u\) 子树，向上覆盖到的深度为 \(k\)。发现状态数就是平方级别了，而且貌似没有办法直接优化这个状态，那么就考虑使用数据结构维护。

先从转移入手，发现对于每个节点需要维护最小的 \(f_{u,k}\)。那么就需要可以维护最小值的数据结构。线段树貌似有点难做，那么就考虑堆。对于一个儿子 \(v\)，\(f_{v,k}\) 能为 \(f_{u,k}\) 带来 \(f_{v,k} + \sum _{j \in sub(u) \wedge j \not = v} f_j\) 的贡献，这个只需在堆上维护整体加一个数即可。

\(u\) 的若干儿子和以 \(u\) 为起点的路径都能为 \(u\) 带来贡献，因此需要使用可并堆。注意到 \(k > dep_u\) 时不合法，由于只需维护最小值，直接在堆顶暴力删除即可。

时间复杂度 \(O((n + m) \log m)\)，空间复杂度 \(O(m)\)。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#define mp make_pair
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
	x = 0; int f = 0; char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
	if(f) x = ~x + 1;
}
const int N = 6e5 + 10;
int n, m;
int dep[N];
vector<int> G[N];
vector<pair<LL, int>> path[N];
void dfs1(int u, int fa) {
	for(auto v : G[u]) 
		if(v ^ fa)
			dep[v] = dep[u] + 1, dfs1(v, u);
}
struct node {
	pair<LL, int> val;
	int lc, rc, fa;
	int d;
	LL tag;
}tr[N];
int tot;
#define l tr[x].lc
#define r tr[x].rc
inline int newnode(LL w, int d) {tr[++tot] = (node){mp(w, d), 0, 0, 0, 1, 0}; return tot;}
inline void maintain(int x) {tr[x].d = tr[r].d + 1;}
inline void add(int x, LL v) {tr[x].val.first += v, tr[x].tag += v;}
inline void pushdown(int x) {
	if(!tr[x].tag) return;
	add(l, tr[x].tag), add(r, tr[x].tag);
	tr[x].tag = 0;
}
int merge(int x, int y) {
	if(!x || !y) return x | y;
	if(tr[x].val > tr[y].val) swap(x, y);
	pushdown(x);
	tr[r = merge(r, y)].fa = x;
	if(tr[l].d < tr[r].d) swap(l, r);
	maintain(x);
	return x;
}
#undef l
#undef r
int rt[N];
LL f[N];
void dfs(int u, int fa) {
	LL sum = 0;
	for(int v : G[u])
		if(v ^ fa)
			dfs(v, u), sum += f[v];
	for(int v : G[u]) 
		if(v ^ fa)
			add(rt[v], sum - f[v]),
			rt[u] = merge(rt[u], rt[v]);
	for(auto x : path[u]) 
		rt[u] = merge(rt[u], newnode(sum + x.first, x.second));
	if(u > 1) while(rt[u] && tr[rt[u]].val.second >= dep[u])
		pushdown(rt[u]), rt[u] = merge(tr[rt[u]].lc, tr[rt[u]].rc);
	else while(rt[u] && tr[rt[u]].val.second)
		pushdown(rt[u]), rt[u] = merge(tr[rt[u]].lc, tr[rt[u]].rc);
	if(!rt[u]) {
		puts("-1");
		exit(0);
	}
	f[u] = tr[rt[u]].val.first; 
}
int main() {
	read(n), read(m);
	for(int i = 1, u, v; i < n; ++i)
		read(u), read(v), 
		G[u].emplace_back(v), G[v].emplace_back(u);
	dfs1(1, 0);
	if(n == 1) {puts("0"); return 0;}
	for(int i = 1, x, y, w; i <= m; ++i) {
		read(x), read(y), read(w);
		path[x].emplace_back(mp(w, dep[y]));
	}
	dfs(1, 0);
	printf("%lld\n",f[1]);
	return 0;
}