C26H:Register Allocation

http://poj.openjudge.cn/practice/C26H/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> leftChild(n + 1, 0), rightChild(n + 1, 0);

    string a, b;
    cin >> a >> b; // root placeholder: "- -"

    for (int i = 2; i <= n; i++) {
        int p;
        char d;
        cin >> p >> d;

        if (d == 'L') {
            leftChild[p] = i;
        } else {
            rightChild[p] = i;
        }
    }

    vector<int> dp(n + 1, 0);

    for (int u = n; u >= 1; u--) {
        int l = leftChild[u];
        int r = rightChild[u];

        if (l == 0 && r == 0) {
            dp[u] = 1;
        } else if (l != 0 && r == 0) {
            dp[u] = dp[l];
        } else if (l == 0 && r != 0) {
            dp[u] = dp[r];
        } else {
            int x = dp[l];
            int y = dp[r];

            if (x == y) {
                dp[u] = x + 1;
            } else {
                dp[u] = max(x, y);
            }
        }
    }

    cout << dp[1] << '\n';

    return 0;
}

这道题目要求计算一棵二叉树的特定“阶数”或“维度”（逻辑类似于斯特拉勒阶数 Strahler Stream Order）。

Python 代码实现

import sys

def solve():
    # 使用 sys.stdin.read().split() 一次性读取所有输入，提高在大数据量下的性能
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    if n == 0:
        return

    # 初始化左孩子和右孩子数组，0 表示没有孩子
    left_child = [0] * (n + 1)
    right_child = [0] * (n + 1)

    # 跳过根节点的占位符（即输入中的 "- -"）
    # input_data[1] 和 input_data[2] 分别是根节点的占位信息
    
    # 从第 3 个元素开始，每两个一组表示 parent 和 direction
    idx = 3
    for i in range(2, n + 1):
        p = int(input_data[idx])
        direction = input_data[idx + 1]
        idx += 2
        
        if direction == 'L':
            left_child[p] = i
        else:
            right_child[p] = i

    # dp[u] 表示以 u 为根的子树的计算值
    dp = [0] * (n + 1)

    # 按照节点编号从大到小遍历。
    # 这种遍历方式的前提是：父节点的编号一定小于子节点的编号（题目输入逻辑通常满足此点）。
    # 如果不满足，则需要使用后序遍历（DFS）。
    for u in range(n, 0, -1):
        l = left_child[u]
        r = right_child[u]

        if l == 0 and r == 0:
            # 情况 1：叶子节点，初始值为 1
            dp[u] = 1
        elif l != 0 and r == 0:
            # 情况 2：只有左孩子，继承左孩子的值
            dp[u] = dp[l]
        elif l == 0 and r != 0:
            # 情况 3：只有右孩子，继承右孩子的值
            dp[u] = dp[r]
        else:
            # 情况 4：左右孩子都有
            x = dp[l]
            y = dp[r]
            if x == y:
                # 如果两个孩子值相等，当前节点值加 1
                dp[u] = x + 1
            else:
                # 如果不等，取较大的那个值
                dp[u] = max(x, y)

    # 输出根节点（1号节点）的计算结果
    print(dp[1])

if __name__ == "__main__":
    solve()

---

代码解读

1. 核心 DP 逻辑

这道题的核心在于处理节点合并时的规则：

• 叶子节点：基础权重为 $1$。
• 单分支节点：权重不增加，直接传递子节点的值。
• 双分支节点：
  • 如果两个子树的“复杂度”相同（x == y），说明当前节点需要更高一阶的复杂度来协调，因此 +1。
  • 如果不同，则当前节点的复杂度由那个较复杂的子树决定。

2. 遍历顺序

C++ 代码中使用 for (int u = n; u >= 1; u--) 是为了模拟从叶向根的计算过程。

• 在二叉树问题中，如果节点 $i$ 的父节点编号总是小于 $i$，那么从 $n$ 到 $1$ 的逆序遍历就等同于拓扑排序的逆序，也就是保证了在计算父节点时，子节点已经计算完毕。

3. 性能处理

• 数据读取：sys.stdin.read().split() 在处理 POJ 这种输入行数非常多的题目时，比 input() 快很多，因为它减少了系统调用的次数。
• 空间复杂度：使用了三个长度为 $n+1$ 的数组，空间复杂度为 $O(n)$，符合题目要求。

4. 树的表示

代码没有使用复杂的类结构（如 Node 对象），而是使用了静态数组（left_child, right_child）来表示树。这种方法在算法竞赛中非常流行，因为它在 Python 中比对象引用更省内存，运行也更快。