「KTSC 2022 R1」进化 题解

问题分析

我们有一个动态增长的进化树，每个非叶子节点需要选择一条出边作为主要进化，其他出边作为次要进化。进化复杂度定义为：任意两个生物体路径上次要进化数量的最大值。

关键转化：这等价于一个树的半径最小化问题。选择主要进化路径相当于在树中选择一条中心路径，使得所有节点到这条路径的距离最大值最小。

核心思路

问题重新定义

对于以节点 $R$ 为根的子树：

• 每个非叶子节点选择一条出边作为主要边
• 目标：最小化根到所有叶子的路径上次要边数量的最大值
• 这等价于求树的半径：所有节点到主要路径的最大距离

半径计算规则

设节点 $x$ 的子节点半径排序为 $d_1 \geq d_2 \geq \cdots \geq d_k$：

1. 选择 $d_1$ 对应的边作为主要边时：

   • 主要路径继承半径 $d_1$
   • 其他路径半径变为 $d_i + 1$（多一条次要边）
   • $x$ 的半径 = $\max(d_1, d_2+1)$

2. 递推公式：

   • 叶子节点：半径 = 0
   • 内部节点：半径 = $\max(d_1, d_2+1)$，其中 $d_1, d_2$ 是最大的两个子节点半径

算法实现详解

数据结构设计

struct node {
    int mxv = 0;        // 当前最大半径值
    int c[20];          // 各半径值的出现次数（深度限制优化）
    
    // 插入新的半径值
    inline void ins(int x) {
        mxv = max(mxv, x);
        c[x]++;
    }
    
    // 半径值增加1（子节点更新时）
    inline void mdf(int x) {
        mxv = max(mxv, x + 1);
        c[x]--;
        c[x + 1]++;
    }
    
    // 计算新的最大半径
    inline int qry() {
        return c[mxv] > 1 ? mxv + 1 : mxv;
    }
    
    // 计算当前子树的进化复杂度（树的半径）
    inline int val() {
        if (!c[mxv]) return 0;                    // 叶子节点
        
        // 情况1：多个最大半径，必须增加整体半径
        if (c[mxv] > 2) return (mxv + 1) << 1;    
        
        // 情况2：两个最大半径，形成平衡
        if (c[mxv] == 2) return mxv << 1 | 1;     
        
        // 情况3：一个最大半径 + 次大半径
        int sec = -1;
        for (int i = mxv - 1; ~i; i--) {
            if (c[i]) { sec = i; break; }
        }
        return mxv + sec + 1;  // max(d1, d2+1) 的变形
    }
} a[MAXN];

关键操作函数

// 向上传播答案更新
inline void mdf_ans(int p, int v) {
    if (!p) return;
    if (ans[p] < v) {
        ans[p] = v;
        mdf_ans(fat[p], v);
    }
}

// 处理子节点半径变化
inline void mdf(int x, int y) {
    int cpy = f[x];
    a[x].mdf(f[y] - 1);    // 更新半径分布
    f[x] = a[x].qry();     // 重新计算最大半径
    
    mdf_ans(x, a[x].val()); // 更新当前节点答案
    
    // 如果半径增加，继续向上传播
    if (f[x] > cpy) {
        mdf(fat[x], x);
    }
}

主要接口实现

void observation(int P) {
    n++;
    fat[n] = P;
    int cpy = f[P];
    
    // 添加新子节点（初始半径0）
    a[P].ins(0);
    f[P] = a[P].qry();
    
    // 如果父节点半径变化，向上传播
    if (f[P] > cpy) {
        mdf(fat[P], P);
    }
    
    // 更新当前节点答案
    mdf_ans(P, a[P].val());
}

int analyze(int R) {
    return ans[R];  // 直接返回预计算的半径
}

算法正确性证明

半径计算正确性

对于节点 $x$ 的子节点半径 $d_1 \geq d_2 \geq \cdots \geq d_k$：

• 情况1（$c[mxv] > 2$）：多个子节点达到最大半径，选择任一个作为主要边都会使其他路径半径+1
• 情况2（$c[mxv] = 2$）：两个子节点达到最大半径，形成平衡
• 情况3（$c[mxv] = 1$）：一个最大半径，次大半径决定整体半径

更新传播正确性

当子节点半径变化时：

1. 更新父节点的半径分布
2. 重新计算父节点半径
3. 如果半径增加，继续向上传播
4. 保证所有祖先节点的半径信息都是最新的

复杂度分析

时间复杂度

• 单次 observation：均摊 $O(\log N)$
  • 半径分布更新：$O(1)$
  • 答案传播：树高相关
• 单次 analyze：$O(1)$（答案预计算）
• 总复杂度：$O((N+Q) \log N)$

空间复杂度

• 树结构：$O(N)$
• 半径分布：$O(20N)$（利用深度限制）
• 总空间：$O(N)$

算法优势

1. 在线算法：支持动态建树和实时查询
2. 高效更新：只更新受影响路径，避免全树重构
3. 答案预计算：analyze 操作直接返回，无额外计算
4. 深度优化：利用半径深度有限的特性进行优化

总结

本题通过将进化复杂度问题转化为树的半径最小化问题，设计了一个高效的在线算法。利用半径分布的统计信息和自底向上的传播更新，在 $O((N+Q)\log N)$ 时间内解决了大规模动态树的半径计算问题。

核心洞察：选择主要进化路径等价于在树中选择中心路径，最小化所有节点到中心路径的最大距离，这正是树的半径问题的本质。