P8238 避难所 题解
dspt
·
·
题解
1.前置知识
线段树 和 DFS 序
建议做 DFS 序 2 来练练手（其实跟这题差不多）
2.思路
对于题目中的操作，$1$ 是树上单点修改，$2$ 是子树修改，每修改一遍后求一次根节点的值。
对于两个操作，直接做的话很可能被卡，于是我们将这棵树的 DFS 序预处理出来。**每一棵子树的 DFS 序是连续的。** 那么子树修改就可以放到线段树上做区间修改。线段树根据 DFS 序为**叶子节点**建树。即**原树**上节点 $i$ 在**线段树**建树前的数组中对应的是 $\text{dfn}_i$。
这样 $\log n$ 就可以做完了，可是直接查询仍然很慢，每一次时间复杂度可能被卡到 $O(n)$，这样显然会超时，于是我们得想办法优化。
**原树**上，对于每一个节点 $i$，我们记录 $v$ 为值，$c$ 为所有 $i$ 的子树内与 $i$ **不连通路径数量最小的** $v$ 之和。在**线段树**上也是类似的，每次查询是 $O(1)$ 的。
但这样的话，修改会变慢，于是我们记录 $min_i$ 为**原树**上节点 $i$ 到根节点中封闭的路段数的**最小值**。如果 $min_i>0$ 那么答案为 $0$。
## 3. 线段树 `push`
对于一个节点，我们现在有 $5$ 个值，$L,R,min, c, v,tag$。直观地，$v$ 可以省去（并到 $c$ 中）。`push` 应该是最难的一个部分。
对于 `pushup`，我们主要考虑 $i$ 左子树 $ls$ 和右子树 $rs$ 的 $min$。
$$
c_i=\begin{cases}
c_{ls}+c_{rs}&min_{ls}=min_{rs}\\
c_{ls}&min_{ls}<min_{rs}\\
c_{rs}&min_{rs}<min_{ls}
\end{cases}
$$
$$min_i =\min(min_{ls},\ min_{rs})$$
对于 `pushdown`，因为区间修改主要修改的是 $min$，所以将懒标记都加到 $min$ 上就好了。
## 4. 代码
```cpp
#include <vector>
#include <stdio.h>
using namespace std;
const int _(100005);
vector<int> E[_]; // 记录原树的边
typedef long long ll; ll C[_ << 2];
bool d[_]; // 用来记录一个节点是否与其父节点连通（2操作）
int n, q, t, x, y, dfn[_], a[_], b[_], s[_];
// DFS 需要用的变量，用小写区分；dfn 是 dfs 序，a 是原树各节点的值，b 是线段树建树前数组的值，s 是原树中各节点的子树大小
int L[_ << 2], R[_ << 2], M[_ << 2], T[_ << 2];
// 线段树中的变量，用大写区分；M 是 min, T 是懒标记
void DFS(int p, int fa)
{ b[dfn[p] = ++t] = a[p]; for (int i : E[p]) if (i != fa) dfs(i, p), s[p] += s[i]; }
// 一遍 DFS 求出 dfn
#define ls p << 1
#define rs p << 1 | 1
void pushup(const int p)
{
if (M[ls] == M[rs]) { M[p] = M[ls]; C[p] = C[ls] + C[rs]; }
else if (M[ls] < M[rs]) { M[p] = M[ls]; C[p] = C[ls]; }
else { M[p] = M[rs]; C[p] = C[rs]; }
}
inline void pushdown(const int p)
{ if (T[p]) { T[ls] += T[p]; M[ls] += T[p]; T[rs] += T[p]; M[rs] += T[p]; T[p] = 0; } }
inline void build(const int p, const int l, const int r) // 线段树模板 × 1
{
R[p] = r, L[p] = l; int m = (l + r) >> 1;
if (l == r) { M[p] = T[p] = 0; C[p] = b[l]; return; }
// min 与懒标记一开始赋值为 0
build(ls, l, m); build(rs, m + 1, r); pushup(p);
}
void change(const int p) // 线段树模板 × 2
{
if (L[p] == R[p]) { C[p] = y; return; }
pushdown(p); int m = (L[p] + R[p]) >> 1;
if (x <= m) change(ls);
else change(rs);
pushup(p);
}
void add(const int p, const int v) // 线段树模板 × 3
{
if (x <= L[p] && R[p] <= y) { T[p] += v; M[p] += v; return; }
pushdown(p); int m = (L[p] + R[p]) >> 1;
if (x <= m) add(ls, v);
if (m < y) add(rs, v);
pushup(p);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i(1), u, v; i < n; ++i)
scanf("%d%d", &u, &v),
E[u].emplace_back(v),
E[v].emplace_back(u);
for (int i(1); i <= n; ++i) scanf("%d", &a[i]), s[i] = 1; // 初始每个原树节点的大小为 1
dfs(1, 0); build(1, 1, n);
while (q--)
{
scanf("%d%d", &t, &x);
if (t & 1) { scanf("%d", &y); x = dfn[x]; change(1); }
// dfn[x] 是 x 在线段树上的位置
else
{
y = dfn[x] + s[x] - 1; x = dfn[x];
// 原树上节点 x 在线段树上的区间为 [dfn[x], dfn[x] + s[x])
if (d[x]) add(1, -1);
else add(1, 1); d[x] ^= 1;
}
if (M[1]) puts("0"); // 如果 min 1 > 0，答案为 0
else printf("%lld\n", C[1]);
}
return 0;
}
```