51nod-1462 数据结构 -- 解题报告

题意简述
¶

一棵 $N$ 个节点的树，以 $1$ 为根。树上的每个节点有两个权值： $v_{i}$ ， $t_{i}$ 。初始时均为 $0$ 。有 $Q$ 次操作，每次操作为下列之一：

1 u d: 对 $u$ 到根上所有点执行 $v_{i} + = d$
2 u d: 对 $u$ 到根上所有点执行 $t_{i} + = v_{i} \times d$

输出 $Q$ 次操作后所有节点的 $t_{i}$ 权值。

数据范围： $N, Q ⩽ 10^{5}$ 。
数据保证 $64$ 位整数不会溢出。

题目简析
¶

虽然是树上的链的问题，但是通过树链剖分可以将其拆解成 $O (\log N)$ 段区间，因此我们只考虑如何在区间上完成这两个操作就好了。对于区间维护/查询问题，不难想到使用线段树来处理。

更新操作
¶

给线段树上的每个节点维护三个值 $V_{x}$ , $T_{x}$ 和 $S_{x}$ ，分别表示节点 $x$ 所代表的区间中的所有节点 $i$ 均需要执行：

\begin{aligned} v_{i} + = V_{x} \\ t_{i} + = v_{i} \times T_{x} + S_{x} \end{aligned}

下面考虑两种操作对应的线段树更新流程：

操作一：给 $v_{i}$ 增加值 $d$
若此时 $T_{x}$ 不为 $0$ ，则需要执行一次pushdown操作：将 $T_{x}$ 更新给左右子树，并且将 $T_{x} \times V_{x}$ 累加到 $S_{x}$ 中，最后将 $T_{x}$ 设置为 $0$ .
pushdown.cpp
1 2 3 4 5 6 7 8 9 10 11 void pushdown(int o, int lft, int rht) { LL d = T[o]; if (d == 0) return; T[o] = 0; S[o] += V[o] * d; if (lft < rht) { T[lc] += d; T[rc] += d; } }
为什么要先执行一次pushdown呢？因为此时 $T_{x}$ 代表的是在此次操作之前，节点 $x$ 所代表的区间中所有的点 $i$ 均需要加上 $v_{i} \times T_{x}$ ，如果不先pushdown 则含义变成了 $x$ 所代表的区间中所有的点 $i$ 均需要加上 $(v_{i} + d) \times T_{x}$ .
之后，如果当前节点在目标区间内，则给 $V_{x}$ 加上 $d$ 。由此，不难写出操作一对应的线段树操作的代码：
update1.cpp
1 2 3 4 5 6 7 8 9 10 11 12 void update1(int o, int lft, int rht) { pushdown(o, lft, rht); if (ul <= lft && rht <= ur) { V[o] += uv; return; } int mid = (lft + rht) >> 1; if (ul <= mid) update1(lc, lft, mid); if (ur > mid) update1(rc, mid + 1, rht); }
操作二：给 $t_{i}$ 增加值（ $v_{i}$ 和 $d$ 的乘积）
操作二比操作一略微复杂一些，除了要执行pushdown，还需要将沿途所有的 $V_{s} \times d$ 累加起来（不妨记为 $a c c$ ），直到到达在操作区间内的区间节点时，再将 $a c c$ 累加给 $S$ ，同时将 $d$ 累加给 $T$ .
之所以要记录 $a c c$ 是因为在pushdown操作中我们只往子节点传递了 $T$ ，而没有传递 $V$ ^[1]，因此当前节点 $x$ 的所有祖先节点的 $V$ 值之和 $\sum_{a n c i e n t o f x} V$ 对于此次操作二中 $v_{i}$ 的值都是有贡献的，所以必须维护这部分结果。幸运的是，对于 $x$ 所代表的区间中的所有点， $\sum_{a n c i e n t o f x} V$ 对它们是等效的，所以将其累加到 $S$ 中即可完成这部分信息的维护。
update2.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 void update2(int o, int lft, int rht, LL acc) { if (ul <= lft && rht <= ur) { T[o] += uv; S[o] += acc; return; } acc += V[o] * uv; pushdown(o, lft, rht); int mid = (lft + rht) >> 1; if (ul <= mid) update2(lc, lft, mid, acc); if (ur > mid) update2(rc, mid + 1, rht, acc); }

查询操作
¶

为方便表述，记原树中节点 $i$ 对应线段树中节点 $u (i)$ ，并记 $P_{x}$ 为线段树中节点 $x$ 的所有祖先节点集合，则原树中节点 $i$ 最终的权值为：

\begin{aligned} v_{i} = \sum_{x \in P_{u (i)}} V_{x} \\ t_{i} = S_{u (i)} + \sum_{x \in P_{u (i)}} (\sum_{y \in P_{x}} V_{y} \times T_{x}) \end{aligned}

在线段树中执行一次树上的递推（从根结点出发，沿途pushdown即可），则可以在 $O (N)$ 的复杂度内完成查询。其实若是要多次单个节点的 $t_{i}$ 值，利用现在维护的信息也可以在 $O (\log N)$ 的复杂度内完成。

query.cpp

1
2
3
4
5
6
7
8
9
10
11
12
void query(int o, int lft, int rht) {
  if (lft == rht)
    ans[lft] = S[o] + V[o] * T[o];
  else {
    pushdown(o, lft, rht);
    S[lc] += S[o];
    S[rc] += S[o];
    int mid = lft + rht >> 1;
    query(lc, lft, mid);
    query(rc, mid + 1, rht);
  }
}

复杂度分析
¶

update1 和 update2 都是线段树的经典操作，复杂度均为 $O (\log N)$ ，共执行了 $Q$ 次；query 操作的复杂度和遍历树的复杂度相同，所以是 $O (N)$ 的，共只执了行一次。需要注意的是，update 和 update2 是在树链剖分的基础上进行的，因此其复杂度需要再乘以 $O (\log N)$ ：

空间复杂度: $O (N)$
时间复杂度: $O (Q \log^{2} N + N)$

小结
¶

数据范围比较大，会爆栈，需要手动扩栈 ^[2]。
1 #pragma comment(linker, "/STACK:102400000,102400000")

记区间长度为 $2^{t} < N ⩽ 2^{t + 1}$ ，则线段树至多只需要 $2^{t + 2}$ 个节点。此外，预处理阶段（读入边时）使用到的数组可以和后续线段树中的数组进行复用，以此节约空间

variables.cpp

1
2
3
4
5
6
7
8
9
10
typedef long long LL;
const int MAXN = 100000 + 10;
const int MAXN2 = (1 << 17) + 10;

int N, Q;
int father[MAXN], dep[MAXN], son[MAXN], pos[MAXN], top[MAXN], dfsCnt;
LL V[MAXN2 << 1], T[MAXN2 << 1], S[MAXN2 << 1], ans[MAXN];

// 复用空间
LL *from = V, *to = T, *nxt = S, *siz = ans;

思路上是将操作分解，利用乘法分配律将操作二分解成两部分。总的来说还是利用了线段树维护区间的特点，每次pushdown（或maintain）都不能递归引发子节点的更新操作，则可以证明每次操作至多执行 $O (\log N)$ 次pushdown（或maintain），故而将单次操作的时间复杂度控制在 $O (\log N)$ 内

题意简述¶

题目简析¶

更新操作¶

查询操作¶

复杂度分析¶

小结¶

Related¶