题解 CF1278E 【Tests for problem D】

@土田共戈 的题解说得很好，但是此题不需要什么启发式合并。

构造策略：

遍历节点 x 的每个儿子，分别处理这些儿子对应的子树。此时这些儿子的右端点尚未确定。

新安排一个位置（idx++），它是 x 的左端点。

逆序遍历 xx 的每个儿子，依次向右安排它们的右端点（idx++）。

具体见代码。

也推荐看@土田共戈 的图解。

#include <bits/stdc++.h>
using namespace std;

int N;
int lnk[500005];
int pre[1000005], tgt[1000005], cnt;
void add_E(int u, int v)
{
    pre[++cnt] = lnk[u], tgt[cnt] = v, lnk[u] = cnt;
}

int idx;
int ANSL[500005], ANSR[500005];
int stk[500005], len;
void DFS(int x, int f)
{
    for (int e = lnk[x]; e; e = pre[e])
        if (tgt[e] != f)
            DFS(tgt[e], x);
    for (int e = lnk[x]; e; e = pre[e])
        if (tgt[e] != f)
            stk[++len] = tgt[e];
    ANSL[x] = ++idx;
    while (len)
        ANSR[stk[len]] = ++idx, len--;
}

int main()
{
    scanf("%d", &N);
    for (int i = 1; i < N; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add_E(u, v);
        add_E(v, u);
    }
    DFS(1, 0);
    ANSR[1] = ++idx;
    for (int i = 1; i <= N; i++)
        printf("%d %d\n", ANSL[i], ANSR[i]);
}