题解：P4006 小 Y 和二叉树

AmaoFox · 2024-05-05 20:38:55 · 题解

• 给定一棵树，结点的编号为 1 ~ n，你可以随便安排树的形态（树根和兄弟的顺序），给出其可能的最小的中序遍历。

先最小化中序遍历的第一个点。既然是第一个点，必然没有左儿子，所以 k_x\le 2。

可以选择最小的 k_x \le 2 的点作为中序遍历的第一个点。
如果 k_x = 1，则 x 可以是树根或者某个点的左儿子，否则是某个点的左儿子并且它有一个右儿子。

假设 k_x = 1，那么把 x 唯一的邻居当作它的右儿子，或者把这个邻居当作它的父亲，两种情况总可以找到相同的中序遍历，因此不特别考虑。

现在 k_x = 2，我们需要安排与 x 相连的点的位置（父亲或右儿子）以最小化中序遍历的字典序。

先通过树形 DP 确定每个结点子树中的小问题中的第一个结点，注意到中序遍历中的下一个最小总可以是右儿子的子树中 k_x \le 2 的最小点，之后递归地分情况讨论把哪一个放在右儿子就可以了。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1000005;

int k[N], dp[N];
vector<int> g[N];

bool cmp(const int &x, const int &y) {
  return dp[x] < dp[y];
}

void dfs(int u, int fa) {
  if(k[u] <= 2) {
    dp[u] = u;
  } else {
    dp[u] = 1145141919810;
  }
  for(int v : g[u]) {
    if(v != fa) {
      dfs(v, u);
      dp[u] = min(dp[u], dp[v]);
    }
  }
}

void dfs(int u, int fa, int c) {
  //cout << '>' << u << ' ' << fa << ' ' << c << '\n';
  int ok = 1;
  sort(g[u].begin(), g[u].end(), cmp);
  if(c) {
    for(int v : g[u]) {
      if(v != fa) {
        if(k[u] <= 2) {
          if(dp[v] > u) {
            cout << u << ' ';
            ok = 0;
          }
          dfs(v, u, 1);
        } else {
          dfs(v, u, 1);
          if(ok) {
            cout << u << ' ';
            ok = 0;
          }
        }
      }
    }
    if(ok) {
      cout << u << ' ';
    }
    return;
  }
  cout << u << ' ';
  for(int v : g[u]) {
    if(v != fa) {
      if(k[u] == 2) {
        dfs(v, u, v >= dp[v]);
      } else if(k[u] == 3) {
        dfs(v, u, ok--);
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  int first = 0;
  for(int i = 1; i <= n; i++) {
    cin >> k[i];
    for(int j = 1; j <= k[i]; j++) {
      int v;
      cin >> v;
      g[i].push_back(v);
    }
    if(k[i] <= 2 && !first) {
      first = i;
    }
  }
  g[first].push_back(first);
  k[first]++;
  dfs(first, first);
  dfs(first, first, 0);
}