题解：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]。递归时顺便传参记录一下即可。

代码：

#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;
}