LOJ #146 DFS 序 3，树上差分 1 题解
极其毒瘤的一道题！！！
谨以此题解纪念我逝去的 12 小时 Debug 时光。
不过还是很有收获的，学到了很多新东西。指花了两个小时学习树剖然后发现卡数剖
原题指路
题意简述
给定一棵有根树，有 \(N\) 个节点，依次编号为 \(1,2,\ldots,N\) ，根节点编号为 \(R\) 。有 \(M\) 次操作，分为以下三类：
1 a b x，表示将「结点 \(a\) 到结点 \(b\) 的简单路径」上所有结点的权值都增加 \(x\)；2 a，表示求结点 \(a\) 的权值；3 a，表示求 \(a\) 的子树上所有结点的权值之和。
写在前面
首先，提示几个你可能遇到的坑点。如果你已经有了思路，可以先不看下面的解析，试着从这几点入手调试你的代码。
-
如果你学过树链剖分，你可能会觉得这是一道树剖板子。但是卡树剖。
-
如果你觉得应该要维护区间并且兴致冲冲地写了线段树，对不起，本题卡线段树（不过可以极限卡常过）。
-
据说本题卡倍增 LCA （我没有测试过）。建议使用更快的算法。
-
如果你听信了题面并使用了
fread()和fwrite()快读快写，那么请仔细检查缓冲区的设置。如果你不是非常了解其原理，请不要轻易尝试（亲身经历，会不明所以地 RE ）。其实关闭流同步的cin和cout就已足够（在我的程序上测试过）。
接下来是正文。
思路：dfs 序 + 树上差分 + LCA + 树状数组
首先，题面说的非常清晰，我就不翻译题意了。
第一个需要我们实现的是路径修改。不难想到使用树上差分，而且是点差分。不过很快我们就遇到一个问题：一般情况下，做树上差分后，我们要想求得每个节点的权值，应当对树做一次 dfs 。但题上同时还塞入了巨量的查询，用 dfs 肯定是不现实的。怎么办呢？
我们先看剩下的要求。
第二个要求是单点查询，第三个要求是子树查询。子树查询提醒了我们也许应该使用 dfs 序。不过 dfs 序怎么和前两个要求结合起来呢？
答案是：dfs 序不影响树上差分，只需要在 dfs 序列上按原方法差分就好了。而回顾树上前缀和的定义，我们要想在差分树上求单点权值，其实就是求它的差分子树的子树和。这也侧面印证了 dfs 序的正确性。我们的解法就应该围绕 dfs 序展开。注意，这里差分树的概念是我定义的，可以类比数组中的原数组和差分数组的关系。
总结一下，我们现在应该先跑一遍 dfs 得到原树的 dfs 序；然后在 dfs 序上建立差分数组，把原树上每个点的权值差分地加进去；然后求解单点权值 \(w_u\) 的时候，我们直接统计其子树权值和，也就是 dfs 序的差分数组中 \([in_u, out_u]\) 这一段的区间和。
接下来看子树和怎么求。有了上面的铺垫，我们能想到，子树上的每个节点都可以用上面单点求值的方法求得；再把它们加到一起即可。但是直接暴力累加也不现实。怎么做呢？我们写出式子来观察：
解释一些变量名：\(ans_u\) 是以 \(u\) 为根的子树和，\(in_u\) 和 \(out_u\) 记录 dfs 序，\(id_i\) 表示在 dfs 序中处在第 \(i\) 位的那个节点的编号，\(d_j\) 是上文差分数组。
观察式子并手动模拟，不难发现每个 \(d_j\) 总共被累加了 \(dep_{id_j} - dep_{fa_{u}}\) 次，其中 \(dep_u\) 表示节点 \(u\) 的深度，\(fa_u\) 表示 \(u\) 的父亲。
然后我们就可以对式子进行一些小变形：
从这个式子不难看出，我们只要分别维护 \(d_{i}\cdot dep_{id_i}\) 和 \(d_i\) 的前缀和，就能快速得到 \(ans_u\) 。而 \(d_i\) 的前缀和也恰好是查询单点值所要用到的。
现在，问题只剩下最后一步：我们应该找一种高效的数据结构来维护刚才提到的两个量。我们要实现单点修改（因为用到了差分）和区间查询，所以选树状数组。至此，整个问题就解决了。
额外多说一句：因为要快速查询 LCA ，这里推荐一个技巧：dfs 序求 LCA 。具体讲解可以看 这里 和 这里 ，篇幅所限，我就不再赘述了。这是一种能 \(O(n\log n)\) 预处理和 \(O(1)\) 查询的在线 LCA 算法，而且编码极短。
最后上代码，若有没讲到的都在注释里了。
#include<iostream>
#include<cstring>
#define lowbit(x) ((x) & -(x))
#define MIN(x, y) (in[(x)] < in[(y)] ? (x) : (y)) //求LCA要用到
#define ll long long
#define MIKU 0
using namespace std;
//下面是快读快写
template<typename type>
inline void read(type &x) {
x = 0; bool flag(0); char ch = getchar();
while (!isdigit(ch)) flag ^= ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
flag ? x = -x : 0;
}
template<typename type,typename ...T> //加了可变参数模板，用起来更方便
inline void read(type &x,T&...y){read(x),read(y...);}
template<typename type>
inline void write(type x, bool flag = 1) {
x < 0 ? x = -x, putchar('-') : 0; static short Stack[50], top(0);
do Stack[++top] = x % 10, x /= 10; while (x);
while (top) putchar(Stack[top--] | 48);
flag ? putchar('\n') : putchar(' ');
}
const int N = 1e6 + 5;
//前向星存图
struct Edge { int v, nxt; } G[2*N];
int h[N], tot;
void addEdge(int u, int v) { G[tot] = {v, h[u]}, h[u] = tot ++; }
int n, m, r;
ll v[N], d[N]; //d[]是差分数组
int in[N], out[N], id[N], dep[N], idx; //dfs序相关数组
//下面是dfs序求LCA
int st[25][N];
void st_init() {
for(int i=1; i<=__lg(n); i++) for(int j=1; j+(1<<i)-1<=n; j++) {
st[i][j] = MIN(st[i-1][j], st[i-1][j+(1<<(i-1))]);
}
}
void dfs(int u, int f) {
st[0][in[u] = ++idx] = f, dep[u] = dep[f] + 1, id[idx] = u;
for(int e=h[u]; ~e; e=G[e].nxt) if(G[e].v != f) dfs(G[e].v, u);
out[u] = idx;
}
int LCA(int x, int y) {
if(x == y) return x;
if((x = in[x]) > (y = in[y])) swap(x, y);
int d = __lg(y - x++);
return MIN(st[d][x], st[d][y-(1<<d)+1]);
}
//线段树
struct BIT {
ll c1[N], c3[N]; //c1[]维护d[i]，c3[]维护d[i]*dep[id[i]]
//别问为什么没有c2[]，这是一个悲伤的故事。我最初以为单点查询是区修区查，调了半个多小时。
void build() {
for(int i=1; i<=n; i++) { //O(n) 建树
c1[i] += d[i], c3[i] += 1ll * d[i] * dep[id[i]];
int fa = i + lowbit(i);
if(fa <= n) c1[fa] += c1[i], c3[fa] += c3[i];
}
}
void modify(int x, ll v) {
for(int i=x; i<=n; i+=lowbit(i)) c1[i] += v, c3[i] += 1ll * v * dep[id[x]];
}
ll query_nd(int x) { //单点权值查询（操作2）
ll ans = 0;
for(int i=x; i>0; i-=lowbit(i)) ans += c1[i];
return ans;
}
ll query_subt(int rt, int x) { //子树和查询（操作3）
ll ans = 0;
for(int i=x; i>0; i-=lowbit(i)) ans += c3[i] - 1ll * c1[i] * dep[st[0][in[rt]]];
return ans;
}
} tr;
signed main() {
memset(h, -1, sizeof(h));
read(n, m, r);
for(int i=1; i<=n; i++) read(v[i]);
for(int i=1; i<n; i++) {
int u, v;
read(u, v);
addEdge(u, v), addEdge(v, u);
}
dfs(r, 0);
st_init();
for(int i=1; i<=n; i++) d[in[i]] += v[i], d[in[st[0][in[i]]]] -= v[i]; //把每个点的权值处理到差分数组里。
//式子长这样的原因是同一个点同时是路径起点、终点和LCA，加两次减一次；
//dfs序求LCA后，st[0][in[i]] 存的就是 i 的父亲，下文不再解释。
tr.build();
while(m--) {
ll op, a, b, x;
read(op);
if(op == 1) {
read(a, b, x);
int lca = LCA(a, b);
tr.modify(in[a], x), tr.modify(in[b], x);
tr.modify(in[lca], -x);
if(st[0][in[lca]]) tr.modify(in[st[0][in[lca]]], -x); //树上差分。记得判断0，不然树状数组会死循环。
} else if(op == 2) {
read(a);
write(tr.query_nd(out[a]) - tr.query_nd(in[a]-1));
} else {
read(a);
write(tr.query_subt(a, out[a]) - tr.query_subt(a, in[a]-1));
}
}
return MIKU;
}
完结撒花\o/
浙公网安备 33010602011771号