C++ 破解 4n - 1 结点二叉树优美 DFS 序数量问题：代码、解释与复杂度剖析

以下是解决此问题的 C++ 代码： ```cpp #include <iostream> #include <fstream> #include <vector> #define MOD 1000000007 using namespace std; const int MAXN = 1005; int n; vector<int> adj[MAXN * 4]; int leaf[MAXN * 4]; int dp[MAXN * 4][MAXN * 2][2]; // 深度优先搜索计算优美 DFS 序的数量 void dfs(int u) { if (u > 2 * n) { // 叶子节点 dp[u][0][0] = 1; return; } int l = adj[u][0], r = adj[u][1]; dfs(l); dfs(r); for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (i + j > n) break; // 左子树在前 dp[u][i + j][0] = (dp[u][i + j][0] + 1LL * dp[l][i][0] * dp[r][j][0] % MOD) % MOD; dp[u][i + j][0] = (dp[u][i + j][0] + 1LL * dp[l][i][1] * dp[r][j][0] % MOD) % MOD; dp[u][i + j][0] = (dp[u][i + j][0] + 1LL * dp[l][i][0] * dp[r][j][1] % MOD) % MOD; dp[u][i + j][0] = (dp[u][i + j][0] + 1LL * dp[l][i][1] * dp[r][j][1] % MOD) % MOD; // 右子树在前 dp[u][i + j][1] = (dp[u][i + j][1] + 1LL * dp[r][j][0] * dp[l][i][0] % MOD) % MOD; dp[u][i + j][1] = (dp[u][i + j][1] + 1LL * dp[r][j][1] * dp[l][i][0] % MOD) % MOD; dp[u][i + j][1] = (dp[u][i + j][1] + 1LL * dp[r][j][0] * dp[l][i][1] % MOD) % MOD; dp[u][i + j][1] = (dp[u][i + j][1] + 1LL * dp[r][j][1] * dp[l][i][1] % MOD) % MOD; } } } int main() { ifstream fin("tree.in"); ofstream fout("tree.out"); int c; fin >> c; fin >> n; for (int i = 1; i <= 2 * n - 1; i++) { int l, r; fin >> l >> r; adj[i].push_back(l); adj[i].push_back(r); } for (int i = 1; i <= n; i++) { int a, b; fin >> a >> b; leaf[a] = leaf[b] = i; for (int j = 0; j <= 4 * n; j++) { for (int k = 0; k <= n; k++) { dp[j][k][0] = dp[j][k][1] = 0; } } dfs(1); fout << (dp[1][i][0] + dp[1][i][1]) % MOD << endl; } fin.close(); fout.close(); return 0; } ``` 代码解释： 1. 输入处理： - 从文件 `tree.in` 中读取测试点编号 `c` 和 `n`。 - 读取二叉树的结构，将每个非叶子节点的左右子节点存储在 `adj` 数组中。 - 读取每次操作选择的两个叶子节点，并将它们标记上相应的数字。 2. 动态规划数组： - `dp[u][i][0]` 表示以节点 `u` 为根的子树，包含 `i` 对相同数字的节点，且左子树在前的优美 DFS 序的数量。 - `dp[u][i][1]` 表示以节点 `u` 为根的子树，包含 `i` 对相同数字的节点，且右子树在前的优美 DFS 序的数量。 3. 深度优先搜索： - 对于叶子节点，初始化 `dp[u][0][0] = 1`。 - 对于非叶子节点，递归计算左右子树的 `dp` 值，然后根据左右子树的组合情况更新当前节点的 `dp` 值。 4. 输出结果： - 每次操作后，调用 `dfs(1)` 计算以根节点为根的子树的优美 DFS 序的数量，并将结果输出到文件 `tree.out` 中。 复杂度分析： - 时间复杂度：每次操作需要进行一次深度优先搜索，每次搜索的时间复杂度为 $O(n^2)$，因此总的时间复杂度为 $O(n^3)$。 - 空间复杂度：主要是 `dp` 数组的空间开销，为 $O(n^2)$。 ######[AI问答 | 1304点数解答 | 2026-02-07 20:35:12]