自动搬运

查看原文

来自洛谷，原作者为

	dspt その日まで 飛ばあげ 嵐がさわってゆくまで

搬运于2025-08-24 22:37:12，当前版本为作者最后更新于2022-05-01 12:25:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

1.前置知识

线段树 和 DFS 序

建议做 DFS 序 2 来练练手（其实跟这题差不多）
 

2.思路

$n$ 个节点被 $n-1$ 条边连通，这显然是以 $1$ 为根节点的一棵树，我们把这棵树叫做原树。

对于题目中的操作，$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. 代码

#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;
}