不跪模样
题目链接：YBT2023寒假Day1 B
题目大意
给你一棵有根数，点有点权，两种操作：
对于所有 x 子树内与 x 距离不超过 2 的点，将其点权加 v。
询问 x 子树中，满足 i<=j 且 i,j 的 LCA 是 x 的数对 (i,j)，它们点权和的和。
思路
首先看这个 LCA 要怎么处理，不难想到，可以用容斥的方法（因为子树之间的方法涉及子树之间不好维护）
就是这个子树里面的点对减去每个儿子子树里面的点对（注意这里面都有 \(i\leqslant j\) 的限制）
然后因为是点权和，我们可以尝试分离两个点，不难发现其实每个点的出现次数都是子树大小 \(+1\)（加一是因为自己跟自己的时候算了两次）
那一个子树 \(x\) 里面的点对的权值和 \(S(x)=(sz_x+1)sum_x\)（\(sz_x\) 是子树大小，\(sum_x\) 是子树权值和）
但是众多的儿子，一个一个减也是不行的。
考虑重链剖分，也就是树链剖分，那问题就是 \(S(x)-S(son_x)-\sum\limits_{y\in x轻儿子}S(y)\)
那前面两个要求的，是单点，那就只跟 \(sum_x\) 有关，于是我们先看看如何维护 \(sum_x\)。
考虑把 \(sum_x\) 的部分分成三部分：
- 一开始就有的或者是或者是加值的时候所有加的点都在子树内的（也就是加的点在子树内）
那这个部分我们可以直接 dfs 序列搞一开始的，然后后面加的因为整个都在子树内，可以直接给上面的一条祖先链都加上 \(v*d2_x\)（设 \(d2_x\) 为 \(x\) 子树内与 \(x\) 距离不超过 \(2\) 的点数）
2. 在 \((fa_x,v)\) 的修改
3. 在 \((fa_{fa_x},v)\) 的修改
那这两个其实差不多，因为一个点影响它贡献量的分别只有一个点，那我们直接在加值的位置打上标记，到时直接问就好。
不过注意的是第二个加的是 \(v*d1_x\)（设 \(d1_x\) 为 \(x\) 字数内与 \(x\) 距离不超过 \(1\) 的点数）
而第三个加的是 \(v\)。
那么就是第三个部分，轻儿子的 \(S(y)\) 和。
那我们设 \(g(x)=\sum\limits_{y\in x轻儿子}S(y)\)
讨论加入一次操作 \((x,v)\)，要如何维护。
考虑类似上面的情况，也分成三种情况讨论：
- 如果 \(y\) 是 \(x\) 的儿子，那 \(g(y)\) 要加上 \(ds_y*v\)（设 \(ds_x\) 是 \(x\) 所有轻儿子 \(z\) 的 \(sz_z+1\) 的和）
- 如果 \(y=x\)，那 \(g(y)\) 要加上 \(ds1_y*v\)（设 \(ds1_y\) 是 \(x\) 所有轻儿子 \(z\) 的 \(d1_z*(sz_z+1)\) 的和）
- 如果 \((y,z)\) 这条边是 \(x\) 到根路径上的一条边（其中 \(z\) 是 \(y\) 的轻儿子），那 \(g(y)\) 要加上 \(d2(x)*v*(sz_z+1)\)（\(d2_x\) 我们上面定义了， \(x\) 子树内与 \(x\) 距离不超过 \(2\) 的点数）
第一个操作，这个儿子的话我们可以直接在父亲那里打标记（事实上这个标记跟上面的标记其实是一样的），那我们要求 \(g(x)\) 的时候先拿出维护的 \(g(x)\)，再加上父亲的标记值乘上那个 \(ds_{x}\) 即可即可。
第二个两个操作，每次操作最多会影响一个点的 \(g\) 值，我们直接修改 \(g\) 值就好。
第三个操作，由于我们只修改轻链，所以在重链剖分上轻链的数量只有 \(\log n\)，所以我们暴力跳到每个轻链去修改 \(g\) 值即可。
（这也是用重链剖分的原因）
那么这题就做好啦，具体的实现可以看代码。
代码
#include<cmath>
#include<cstdio>
#define uint unsigned int
using namespace std;
const int N = 3e5 + 100;
int n, Q, fa[N], le[N], KK, sz[N], son[N], top[N], dfn[N], idfn[N], d1[N], d2[N];
uint w[N], s[N], sum[N], wsum[N], tg[N], g[N], ds[N], ds1[N];
struct node {
int to, nxt;
}e[N];
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void dfs0(int now, int father) {
sz[now] = 1; wsum[now] = w[now]; d1[now] = d2[now] = 1;
for (int i = le[now]; i; i = e[i].nxt) {
dfs0(e[i].to, now); sz[now] += sz[e[i].to]; wsum[now] += wsum[e[i].to];
d1[now]++; d2[now] += d1[e[i].to];
if (sz[e[i].to] > sz[son[now]]) son[now] = e[i].to;
}
}
void dfs1(int now, int father) {
dfn[now] = ++dfn[0]; idfn[dfn[0]] = now;
if (son[now]) {
top[son[now]] = top[now]; dfs1(son[now], now);
}
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != son[now]) {
top[e[i].to] = e[i].to; dfs1(e[i].to, now);
g[now] += wsum[e[i].to] * (sz[e[i].to] + 1);
ds[now] += sz[e[i].to] + 1;
ds1[now] += d1[e[i].to] * (sz[e[i].to] + 1);
}
}
struct XD_tree {
uint f[N << 2], lzy[N << 2];
void up(int now) {
f[now] = f[now << 1] + f[now << 1 | 1];
}
void downa(int now, uint x) {
f[now] += x; lzy[now] += x;
}
void down(int now) {
if (lzy[now]) {
downa(now << 1, lzy[now]); downa(now << 1 | 1, lzy[now]);
lzy[now] = 0;
}
}
void update(int now, int l, int r, int L, int R, uint x) {
if (L <= l && r <= R) {
downa(now, x); return ;
}
down(now); int mid = (l + r) >> 1;
if (L <= mid) update(now << 1, l, mid, L, R, x);
if (mid < R) update(now << 1 | 1, mid + 1, r, L, R, x);
up(now);
}
uint query(int now, int l, int r, int L, int R) {
if (L <= l && r <= R) return f[now];
down(now); int mid = (l + r) >> 1; uint re = 0;
if (L <= mid) re += query(now << 1, l, mid, L, R);
if (mid < R) re += query(now << 1 | 1, mid + 1, r, L, R);
return re;
}
void build(int now, int l, int r) {
if (l == r) {
f[now] = wsum[idfn[l]]; return ;
}
int mid = (l + r) >> 1;
build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
up(now);
}
}T;
uint Sone(int now) {
if (!now) return 0;
uint re = T.query(1, 1, n, dfn[now], dfn[now]);
re += tg[fa[now]] * d1[now];
re += tg[fa[fa[now]]];
return re * (sz[now] + 1);
}
uint Slot(int now) {
uint re = g[now];
re += ds[now] * tg[fa[now]];
return re;
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d %d", &n, &Q);
for (int i = 2; i <= n; i++) scanf("%d", &fa[i]), add(fa[i], i);
for (int i = 1; i <= n; i++) scanf("%u", &w[i]);
dfs0(1, 0); top[1] = 1; dfs1(1, 0);
T.build(1, 1, n);
for (int i = 1; i <= Q; i++) {
int op; scanf("%d", &op);
if (op == 1) {
int x; uint v; scanf("%d %u", &x, &v);
int now = x;
while (now) {
T.update(1, 1, n, dfn[top[now]], dfn[now], v * d2[x]);
now = fa[top[now]];
}
tg[x] += v;
g[x] += ds1[x] * v;
now = x;
while (now) {
now = top[now];
if (fa[now]) g[fa[now]] += d2[x] * v * (sz[now] + 1);
now = fa[now];
}
}
else {
int x; scanf("%d", &x);
printf("%u\n", Sone(x) - Sone(son[x]) - Slot(x));
}
}
return 0;
}