问题分析

本题需要维护一个动态集合 $S$，并在每次操作后快速计算最优连通块 $C$ 对应的 $\max(a,b)$ 最小值。其中：

• $a$ 是连通块 $C$ 中属于 $S$ 的节点数
• $b$ 是不在 $C$ 中的节点的 $w$ 值最大值
• $w_u$ 表示节点 $u$ 的子树中属于 $S$ 的节点数

关键观察

1. 权重性质：每个节点 $u$ 的权重 $w_u$ 等于其子树中 $S$ 集合的节点数量，这具有子树可加性
2. 树结构特性：由于是根为 $1$ 的有根树，包含根的连通块 $C$ 对应树上的一个子树结构
3. 平衡思想：最优解需要在 $a$（选中的 $S$ 节点数）和 $b$（未选节点的最大权重）之间取得平衡

算法思路

该解法采用以下核心技术：

1. 树链剖分：将树转化为线性结构，便于使用线段树维护

   • 预处理出重链、DFS序等基本信息
   • 支持高效的路径修改操作

2. 线段树维护：维护每个DFS位置对应的信息

   • 支持区间加操作（当 $S$ 集合变化时更新权重）
   • 动态维护关键统计量用于决策

3. 动态调整策略：每次操作后通过比较当前解与可能更优解来调整

   • 当发现更小的 $b$ 值时进行调整
   • 当 $a$ 值可以优化时进行相应修改

复杂度分析

• 预处理：$O(n)$ 的树链剖分
• 每次操作：$O(\log^2 n)$ 的路径修改和线段树操作
• 总体复杂度：$O(n + q\log^2 n)$，能够处理题目中的数据规模

实现要点

算法通过维护两个关键值来指导调整过程：

• 当前选择的连通块大小 $ans$
• 线段树中维护的极值信息

每次集合 $S$ 变化时：

1. 更新受影响节点的权重值
2. 根据权重分布调整连通块选择
3. 输出当前最优的 $\max(a,b)$ 值

这种方法巧妙地利用了树结构的特性和线段树的高效维护能力，在动态环境下快速求出最优解。