题解 CF1278E 【Tests for problem D】
题解 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); ad...