P15408 [NOISG 2026 Prelim] 度数约束生成树 题解

场切了，遂写题解。

首先把形如 1 u w 的边理解成点 的点权 。为方便，删去点 ，将剩下的点编号减去 ，并令 。不妨只保留这 个点的最小生成树。于是题意转化为，对于每个 求出：在 个点中选择 个点，并保留树的一些边，使得选择的 个点恰在 个连通块中，点权和与边权和之和的最小值。

显然， 时选的点一定是 时选的点再加一个点。考虑 的情况，设 是点权最小的点，显然直接选择 即可。考虑 的情况，此时还要选择异于 的一点 ，并删去 到 路径上边权最大的边。发现这个形式很不优雅。因为与最小生成树相关，于是考虑在 Kruskal 重构树上刻画。对 个点建出 Kruskal 重构树，设点 的权值为 ，叶子的权值是原图中的点权，其余点的权值是原图中的边权。此时我们要删除的边就变为了 与 在重构树上的最近公共祖先，于是需要最小化 ，求这个东西是容易的。

考虑 的情况，此时还要选择异于 的一点 ，删去的边是 与 的祖先中离 最近的点 ，并最小化 。 更大的情况也类似：选择一个未被选择的点 ，设 表示 所有已经选择的点的祖先中 离 最近的点，那么删去的边就是 ，并最小化 。显然，每个非叶子节点只会被删除一次。

考虑如何维护这个过程。对于树上的每个点，维护它是否是一个被选择的点的祖先，下文中称作“是否被标记”。对于叶子节点，使用一棵线段树维护 的最小值与最小值位置，设当前最小值位置为 ，则加入点 。从点 向上跳，直到跳到一个被标记的点（即 ）。每跳到一个点就标记这个点，并更新该点的子树。具体地，若上一个经过的点是当前点的左儿子，那么在线段树上更新当前点右儿子的子树；反之则更新当前点左儿子的子树。注意还需要把点 在线段树上的权值赋为极大值。

至于时间复杂度，因为每个点只会被标记一次，所以是 的。

这题有完全一样的 原，不知道为啥 codechef 上有一车又短又快的代码，没仔细看，不管了。

Code

#include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i <= (e); ++i)
using namespace std;

int n, m, val[200005], cnt, cur, rt, fa[200005], ls[200005], rs[200005], lft[200005], rgt[200005], dfn[100005], rnk[100005];
long long ans;
bool tag[200005];
struct edge {
	int u, v, w;
	edge() {}
	edge(int uu, int vv, int ww) { u = uu, v = vv, w = ww; }
} e[200005];

struct dsu {
	int f[200005];
	void init() {
		rep(i, 1, 2 * n - 1) {
			f[i] = i;
		}
	}
	int find(int x) {
		return f[x] == x ? x : f[x] = find(f[x]);
	}
	void merge(int x, int y, int z) {
		x = find(x);
		y = find(y);
		if(x == y) return;
		ans += z;
		f[x] = f[y] = fa[x] = fa[y] = ++cur;
		ls[cur] = x, rs[cur] = y;
		val[cur] = z;
	}
} dsu;

void dfs(int u) {
	lft[u] = cnt + 1;
	if(u <= n) {
		rnk[dfn[u] = ++cnt] = u;
	} else {
		dfs(ls[u]);
		dfs(rs[u]);
	}
	rgt[u] = cnt;
}

struct Segtree {
	int tr[400005], pos[400005], lz[400005];
	void pushup(int p) {
		tr[p] = min(tr[p << 1], tr[p << 1 | 1]);
		pos[p] = tr[p << 1] < tr[p << 1 | 1] ? pos[p << 1] : pos[p << 1 | 1];
	}
	void update(int p, int d) {
		tr[p] += d, lz[p] += d;
	}
	void pushdown(int p) {
		if(lz[p]) {
			update(p << 1, lz[p]);
			update(p << 1 | 1, lz[p]);
			lz[p] = 0;
		}
	}
	void build(int l, int r, int p) {
		lz[p] = 0;
		if(l == r) {
			tr[p] = val[rnk[l]];
			pos[p] = l;
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, p << 1);
		build(mid + 1, r, p << 1 | 1);
		pushup(p);
	}
	void update(int l, int r, int p, int s, int t, int d) {
		if(s <= l and r <= t) {
			update(p, d);
			return;
		}
		pushdown(p);
		int mid = (l + r) >> 1;
		if(s <= mid) update(l, mid, p << 1, s, t, d);
		if(t > mid) update(mid + 1, r, p << 1 | 1, s, t, d);
		pushup(p);
	}
} tr;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m, --n;
	rep(i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		if(u > v) swap(u, v);
		if(not u) val[v] = w;
		else e[++cnt] = edge(u, v, w);
	}
	sort(e + 1, e + 1 + cnt, [](edge a, edge b){
		return a.w < b.w;
	});
	ans = 0, cur = n;
	dsu.init();
	rep(i, 1, cnt) {
		dsu.merge(e[i].u, e[i].v, e[i].w);
	}
	cnt = 0;
	dfs(cur);
	tr.build(1, n, 1);
	fa[cur] = 0, tag[0] = 1, val[0] = 0;
	rep(k, 1, n) {
		cur = rnk[tr.pos[1]];
		ans += tr.tr[1];
		if(k > 1) cout << ' ';
		cout << ans;
		rt = cur;
		while(not tag[rt]) {
			rt = fa[rt];
		}
		tag[cur] = 1;
		tr.update(1, n, 1, dfn[cur], dfn[cur], 0x3f3f3f3f);
		cur = fa[cur];
		while(cur != rt) {
			tag[cur] = 1;
			if(tag[ls[cur]]) tr.update(1, n, 1, lft[rs[cur]], rgt[rs[cur]], val[rt] - val[cur]);
			else  tr.update(1, n, 1, lft[ls[cur]], rgt[ls[cur]], val[rt] - val[cur]);
			cur = fa[cur];
		}
	}
	cout << '\n';
	return 0;
}