题解：AT_abc240_e [ABC240E] Ranges on Tree

注意到我们划分的最小无交子问题一定是一个叶子节点，令其为

k

，那么答案区间显而易见的为

[1, k]

。

设

dp_x

为点

x

子树中包含的叶子节点个数，则：

dp_x = \sum_{u \in x} dp_u

边界为：

dp_{leaf} = 1

。

dp 序列可以预处理。对于答案的求取，不妨设点

x

当前答案左边界为

pos

，则答案区间为

[pos, pos + dp_x]

。递归时顺便传参记录一下即可。

代码：

CPP

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;

const int N = 1e6 + 5;
int n, u, v, ans, dp[N];
vector<int> g[N];
pair<int, int> Ans[N];

inline void dfs(int x, int last, int pos) {
	int now = pos;

	Ans[x] = {now, now + dp[u] - 1};

	for(auto u : g[x])
		if(u != last) {
			dfs(u, x, now);

			now += dp[u];
		}
	
	return ;
}

inline void init(int x, int last) {
	if(x != 1 && g[x].size() == 1) dp[x] = 1;
	
	for(auto u : g[x])
		if(u != last) {
			init(u, x);

			dp[x] += dp[u];
		}
	
	return ;
}

signed main() {
	ios_base :: sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for(int i = 1 ; i < n ; ++ i) {
		cin >> u >> v;

		g[u].pb(v), g[v].pb(u);
	}

	init(1, -1);
	dfs(1, -1, 1);

	for(int i = 1 ; i <= n ; ++ i)
		cout << Ans[i].fi << ' ' << Ans[i].se << '\n';

	return 0;
}

题解：AT_abc240_e [ABC240E] Ranges on Tree

文章操作

相关推荐

评论

题解：AT_abc240_e [ABC240E] Ranges on Tree