[LOJ#2324]「清华集训 2017」小Y和二叉树
试题描述
小Y是一个心灵手巧的OIer，她有许多二叉树模型。
小Y的二叉树模型中，每个结点都具有一个编号，小Y把她最喜欢的一个二叉树模型挂在了墙上，树根在最上面，左右子树分别在树根的左下方与右下方，且他们也都满足这样的悬挂规则。为了让这个模型更加美观，小Y选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法。所谓中序遍历最小，就是指中序遍历的结点编号序列的字典序最小。
一天，这个模型不小心被掉在了地上，幸运的是，所有结点和边都没摔坏，但是她想不起这个模型原来是怎么悬挂的了，也就是说：她想不起来树根节点的编号了。
小Y最近忙于准备清华集训，所以没太多时间处理别的事情，她只好找到同样心灵手巧的你帮忙复原她的二叉树模型。
给定小Y的二叉树模型，结点的编号为 \(1\) ~ \(n\) ，你需要给出其可能的最小的中序遍历，方便小Y更快的摆好她的模型。
输入
第一行为一个正整数 \(n\) ，表示点的个数。
后接 \(n\) 行，每行若干个整数：
第 \(i+1\) 行的第一个整数为 \(k_i\)，表示编号为 \(i\) 的结点的度数，后接 \(k_i\) 个整数 \(a_{i,j}\)，表示编号为 \(i\) 的结点与编号为 \(a_{i,j}\) 的结点之间有一条边。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
输出
输出共一行， \(n\) 个整数，表示字典序最小的中序遍历。
输入示例
4
3 2 3 4
1 1
1 1
1 1
输出示例
2 1 3 4
数据规模及约定
对于 \(100\%\) 的数据，\(1 \le n \le 1000000, 1 \le k_i \le 3\)。
题解
首先我们可以 dp 出每个节点为根时所能得到的中序遍历最小的第一位。这个就是先随便选一个度数 \(<3\) 的当根，然后正反 dp 一下。
令 \(g_i\) 表示以 \(i\) 为根时最小的中序遍历的第一位（若 \(i\) 度数为 \(3\)，则 \(g_i\) 无意义）。现在可以确定最后答案的第一位一定是 \(min\{g_i\}\)，令 \(r = min\{g_i\}\)，那么我们现在以 \(r\) 为根，求一下 \(f_i\)（即以 \(i\) 为根的子树的中序遍历的最小的第一位），可以发现可以把 \(r\) “看成”根，在填完 \(r\) 的时候，选择一个拥有较小 \(f_i\) 的儿子 \(i\) 递归（在原树中就是把这个儿子甩到右儿子的位置，另一个儿子甩到父亲的位置：即 \(左 \rightarrow 根 \rightarrow 右\) 变成了 \(右 \rightarrow 根 \rightarrow 父节点\)，虽然树的形态改变，但中序遍历本身没有变），然后把另一个儿子接着“看成根”，再递归（注意还有如“只有一个儿子”等特殊情况，注意特判）……以此类推直至遍历完所有节点。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 1000010
#define maxm 2000010
int n, deg[maxn], m, head[maxn], nxt[maxm], to[maxm];
void AddEdge(int a, int b) {
to[++m] = b; nxt[m] = head[a]; head[a] = m;
return ;
}
int f[maxn], g[maxn];
void dp1(int u, int fa) {
f[u] = (fa && deg[u] < 3) ? u : n + 1;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) dp1(to[e], u), f[u] = min(f[u], f[to[e]]);
return ;
}
void dp2(int u, int fa) {
if(fa) g[u] = min(g[fa], deg[fa] < 3 ? fa : n + 1);
else g[u] = n + 1;
int ls = -1, rs = -1;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
if(ls < 0) ls = to[e]; else rs = to[e];
}
if(ls < 0 && rs < 0) return ;
if(rs < 0) {
dp2(ls, u);
g[u] = min(g[u], f[ls]);
return ;
}
int org = g[u];
g[u] = min(org, f[rs]); dp2(ls, u);
g[u] = min(org, f[ls]); dp2(rs, u);
g[u] = min(org, min(f[ls], f[rs]));
return ;
}
int Ans[maxn], cnta;
void dfs(int u, int fa, bool type) {
int ls = -1, rs = -1;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
if(ls < 0) ls = to[e]; else rs = to[e];
}
if(ls < 0 && rs < 0){ Ans[++cnta] = u; return ; }
if(rs < 0) {
if(type) Ans[++cnta] = u, dfs(ls, u, 0);
else {
if(u == f[u]) Ans[++cnta] = u, dfs(ls, u, 0);
else dfs(ls, u, 0), Ans[++cnta] = u;
}
return ;
}
if(f[ls] > f[rs]) swap(ls, rs);
if(type) Ans[++cnta] = u, dfs(ls, u, 0), dfs(rs, u, 1);
else dfs(ls, u, 0), Ans[++cnta] = u, dfs(rs, u, 0);
return ;
}
int main() {
n = read();
int rt;
rep(i, 1, n) {
deg[i] = read();
rep(j, 1, deg[i]) AddEdge(i, read());
if(deg[i] < 3) rt = i;
}
if(n == 1) return puts("1"), 0;
dp1(rt, 0);
dp2(rt, 0);
int root = n + 1;
rep(i, 1, n) root = min(root, g[i]);
// printf("g: "); rep(i, 1, n) printf("%d%c", g[i], i < n ? ' ' : '\n');
dp1(root, 0);
dfs(root, 0, 1);
rep(i, 1, cnta) printf("%d%c", Ans[i], i < cnta ? ' ' : '\n');
return 0;
}