LOZA（COI 2010 T3）题解

题目分析

科学家发现的新物种每个亲本最多繁殖两次，需绘制家谱树并统计非空格字符总数（包括盒型框的 -/|/+/o、样本名字、连接线字符）。核心难点在于：

1. 每个节点的盒型框字符数可固定计算，但亲本有两个子代时，分支线需要横向扩展，需精准计算扩展长度；
2. 物种繁殖特性决定每个节点最多有两个子节点（左/右子，对应繁殖顺序），需基于树形结构处理分支扩展。

核心思路

1. 字符数拆解

将总字符数分为三部分计算：

• 盒型框固定字符：每个节点的盒体包含名字、o、+、-、|，经推导字符数为 $3 \times \text{名字长度} + 6$（代码中 len[i] * 3 + 6）；
• 基础连接字符：亲本首次繁殖（第一个子代）的连接线基础字符数为 3，第二次繁殖（第二个子代）为 1（代码中 ls[x] ? 1 : 3）；
• 分支扩展字符：亲本有两个子代时，分支线需横向扩展，扩展长度由左右子树的深度和扩展需求决定（代码中 ans[i] 记录扩展长度，最终累加 ans[i] << 1）。

2. 树形结构建模

• 每个节点最多两个子节点：ls[u] 表示第一个子代，rs[u] 表示第二个子代；
• 节点深度 dep[u]：表示节点 u 到其最远叶子节点的距离，用于确定分支扩展的有效深度范围；
• 扩展长度 ans[u]：亲本有两个子代时，需计算左右子树在各深度的扩展需求，取最大值作为分支扩展长度。

3. 递归计算扩展长度

• dfsl/dfsr：分别计算左/右子树在各深度的左/右扩展最大值（lt/rt 数组）；
• 遍历有效深度，合并左右子树的扩展需求，确定父节点的分支扩展长度 ans[u]。

解题步骤

1. 初始化与基础字符统计

读取输入，记录每个节点的父节点 fa[i]、名字长度 len[i]、左右子节点 ls[i]/rs[i]； 统计每个节点的盒型框固定字符数（3 * len[i] + 6），以及父子连接的基础字符数（首次繁殖 +3，第二次 +1），累加到总结果 res。

2. 计算节点深度

逆序遍历节点（从 $n$ 到 $2$），更新父节点的深度：dep[fa[i]] = max(dep[fa[i]], dep[i] + 1)，反映节点到最远叶子的距离。

3. 递归计算分支扩展长度

调用 dfs(1) 处理整棵树：

• 若节点有两个子节点：先递归处理左右子节点，确定有效深度 d = min(dep[ls[u]], dep[rs[u]]) + 1；
• 调用 dfsl/dfsr 计算左右子树在各深度的扩展最大值；
• 遍历有效深度，计算 ans[u] = max(lt[i] + rt[i])，并调整为实际扩展长度 (ans[u] + 2) >> 1；
• 若节点只有一个子节点，ans[u] = 0（无分支扩展）。

4. 累加扩展分支字符数

将每个节点的 ans[i] << 1（左右各扩展 ans[i] 个字符）累加到总结果 res，最终输出 res。

复杂度分析

• 时间复杂度：$O(N)$。每个节点仅被递归处理一次，dfsl/dfsr 的遍历深度与节点深度线性相关，整体为线性复杂度，适配 $N \le 3 \times 10^5$ 的数据范围；
• 空间复杂度：$O(N)$。存储节点信息、深度、扩展长度的数组均为线性空间，满足内存限制。

总结

本题的核心是将“图形绘制的字符统计”拆解为固定部分和动态扩展部分，利用树形递归处理动态扩展的分支长度：

1. 先统计固定的盒体和基础连接字符，降低问题复杂度；
2. 基于节点深度确定分支扩展的有效范围，通过分治思想计算左右子树的扩展需求；
3. 线性遍历与递归结合，保证算法效率适配大数据量。

这种“拆解问题+树形建模+分治计算”的思路，是解决复杂图形统计类问题的典型方法，关键在于将图形规则转化为可量化的数值模型，避免直接模拟绘制过程。