[ABC240E] Ranges on Tree 题解
思路解析
由题意可知,只要一个点的所有儿子节点都被确定了,那么当前节点也就被确定了。也就是说,只要确定了所有叶子节点,也就能一层层地确定所有节点,而叶子节点没有儿子节点不受此条件的约束,同时我们希望 \(\max\limits^N_{i=1}R_i\) 最小,所以我们把所有叶子节点的区间长度都置为 \(1\) 即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, fa[N], son[N], cnt = 0, l[N], r[N];
vector<int> g[N];
void dfs(int u, int f) {
fa[u] = f;
for(auto it : g[u]) if(it != f) son[u]++;
if(son[u] == 0) l[u] = r[u] = ++cnt;
else l[u] = 2e9, r[u] = 0;
for(auto it : g[u]) {
if(it != f) dfs(it, u), l[u] = min(l[u], l[it]), r[u] = max(r[u], r[it]);
}
}
int main() {
cin >> n;
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i <= n; i++) {
cout << l[i] << ' ' << r[i] << '\n';
}
return 0;
}
标签:ABC240E,int,题解,son,Ranges,节点
From: https://www.cnblogs.com/2020luke/p/18144216