「CF825G」Tree Queries

发表于 更新于 分类于 本文字数： 316 阅读时长 ≈ 1 分钟

Description

Link：CF825G

给出一棵包含 nn 个点的树，初始时所有点均为白色。

有 QQ 次操作，每次操作形如一下的两种：

  • 1 x：将点 xx 改成黑色。
  • 2 x：对于点 xx，找出编号最小的点 yy，使得 yy 位于 xx 到某个黑色顶点的简单路径上。

**本题强制在线。**保证第一次操作的类型为操作 1。

数据范围：3≤n,Q≤1063 \leq n, Q \leq 10^6。

时空限制：33s / 256256MiB。

Solution

此题相当于维护黑点点集 SS 的最小连通子图的节点编号最小值。

在此题中，黑点不会再重新变回白点。考虑以第一次修改的黑点为根节点 root\mathrm{root}，通过一次 dfs 求出根节点到每个节点 xx 的路径上，节点编号的最小值 dat[x]\mathrm{dat}[x]。

每次新加入一个黑点 xx，就将 xx 到 root\mathrm{root} 路径上的所有点全都加入最小连通子图中（即用 dat[x]\mathrm{dat}[x] 更新答案），显然任意两个黑点之间的所有点均被加入最小连通子图，故该种处理方式是正确的。且由于最小值具有可重复贡献性，故不用考虑去重。