AI004. 树模型推理引擎

# 多树推理:循环走树(深树递归会栈溢出),小于等于阈值走左;
# 多棵树表决取票数最多,平票取数值更小的类别,键=(−票数,类别)。
import sys
from collections import defaultdict


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    at = 0
    t = int(data[at]); at += 1
    d = int(data[at]); at += 1
    q = int(data[at]); at += 1
    trees = []
    for _ in range(t):
        s = int(data[at]); at += 1
        nodes = [None] * (s + 1)
        for i in range(1, s + 1):
            typ = data[at].decode(); at += 1
            if typ == "L":
                nodes[i] = ("L", int(data[at])); at += 1
            else:
                feature = int(data[at]) - 1; at += 1
                threshold = float(data[at]); at += 1
                left = int(data[at]); at += 1
                right = int(data[at]); at += 1
                nodes[i] = ("N", feature, threshold, left, right)
        trees.append(nodes)
    ans = []
    for _ in range(q):
        x = [float(data[at + i]) for i in range(d)]
        at += d
        votes = defaultdict(int)
        for nodes in trees:
            cur = 1
            while nodes[cur][0] != "L":
                _, feature, threshold, left, right = nodes[cur]
                cur = left if x[feature] <= threshold else right
            votes[nodes[cur][1]] += 1
        ans.append(str(min(votes, key=lambda label: (-votes[label], label))))
    print("\n".join(ans))


if __name__ == "__main__":
    solve()