c++给定一棵 4n − 1 个结点的二叉树，其中每个非叶结点都有恰. 好. 两个子结点。非叶 结点编号为 1 到 2n − 1，叶子结点编号为 2n 到 4n − 1。初始时，每个叶子结点上都没 有数字。 定义一个 DFS 序是优. 美. 的. ，当且仅当按该 DFS 序将所. 有. 标. 有. 数. 字. 的. 叶. 子. 结. 点. 上的 数字拼成一个序列时，该序列可以通过若干次消. 除. 相. 邻. 相. 同. 数. 字. 的方式得到空序列。例 如，在下图中，若叶子结点 4, 6 上标有数字 1，叶子结点 5, 7 上标有数字 2，则按 DFS 序 [1, 4, 2, 7, 3, 5, 6] 将所有标有数字的叶子结点上的数字拼成的序列为 [1, 2, 2, 1]，可以通过 消除相邻的 2 的方式得到 [1, 1]，再通过消除相邻的 1 的方式得到空序列，因此该 DFS 序是优美的；而按 DFS 序 [1, 4, 2, 3, 5, 6, 7] 将所有标有数字的叶子结点上的数字拼成的 序列为 [1, 2, 1, 2]，无法通过若干次消除相邻相同数字的方式得到空序列，因此该 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)$。 [2026-02-07 20:35:12 | AI问答 | 1304点数解答]