不跪模样

题目链接：YBT2023寒假Day1 B

题目大意

给你一棵有根数，点有点权，两种操作：
对于所有 x 子树内与 x 距离不超过 2 的点，将其点权加 v。
询问 x 子树中，满足 i<=j 且 i,j 的 LCA 是 x 的数对 (i,j)，它们点权和的和。

思路

首先看这个 LCA 要怎么处理，不难想到，可以用容斥的方法（因为子树之间的方法涉及子树之间不好维护）
就是这个子树里面的点对减去每个儿子子树里面的点对（注意这里面都有 $i⩽j$ 的限制）

然后因为是点权和，我们可以尝试分离两个点，不难发现其实每个点的出现次数都是子树大小 $+1$（加一是因为自己跟自己的时候算了两次）
那一个子树 $x$ 里面的点对的权值和 $S(x)=(s{z}_x+1)su{m}_x$（$s{z}_x$ 是子树大小，$su{m}_x$ 是子树权值和）

---

但是众多的儿子，一个一个减也是不行的。
考虑重链剖分，也就是树链剖分，那问题就是 $S(x)-S(so{n}_x)-\sum _{y\in x轻儿子}S(y)$

那前面两个要求的，是单点，那就只跟 $su{m}_x$ 有关，于是我们先看看如何维护 $su{m}_x$。
考虑把 $su{m}_x$ 的部分分成三部分：

1. 一开始就有的或者是或者是加值的时候所有加的点都在子树内的（也就是加的点在子树内）

那这个部分我们可以直接 dfs 序列搞一开始的，然后后面加的因为整个都在子树内，可以直接给上面的一条祖先链都加上 $v\ast d{2}_x$（设 $d{2}_x$ 为 $x$ 子树内与 $x$ 距离不超过 $2$ 的点数）
2. 在 $(f{a}_x,v)$ 的修改
3. 在 $(f{a}_{f{a}_x},v)$ 的修改

那这两个其实差不多，因为一个点影响它贡献量的分别只有一个点，那我们直接在加值的位置打上标记，到时直接问就好。
不过注意的是第二个加的是 $v\ast d{1}_x$（设 $d{1}_x$ 为 $x$ 字数内与 $x$ 距离不超过 $1$ 的点数）
而第三个加的是 $v$。

---

那么就是第三个部分，轻儿子的 $S(y)$ 和。
那我们设 $g(x)=\sum _{y\in x轻儿子}S(y)$
讨论加入一次操作 $(x,v)$，要如何维护。
考虑类似上面的情况，也分成三种情况讨论：

1. 如果 $y$ 是 $x$ 的儿子，那 $g(y)$ 要加上 $d{s}_y\ast v$（设 $d{s}_x$ 是 $x$ 所有轻儿子 $z$ 的 $s{z}_z+1$ 的和）
2. 如果 $y=x$，那 $g(y)$ 要加上 $ds{1}_y\ast v$（设 $ds{1}_y$ 是 $x$ 所有轻儿子 $z$ 的 $d{1}_z\ast (s{z}_z+1)$ 的和）
3. 如果 $(y,z)$ 这条边是 $x$ 到根路径上的一条边（其中 $z$ 是 $y$ 的轻儿子），那 $g(y)$ 要加上 $d2(x)\ast v\ast (s{z}_z+1)$（$d{2}_x$ 我们上面定义了， $x$ 子树内与 $x$ 距离不超过 $2$ 的点数）

第一个操作，这个儿子的话我们可以直接在父亲那里打标记（事实上这个标记跟上面的标记其实是一样的），那我们要求 $g(x)$ 的时候先拿出维护的 $g(x)$，再加上父亲的标记值乘上那个 $d{s}_x$ 即可即可。
第二个两个操作，每次操作最多会影响一个点的 $g$ 值，我们直接修改 $g$ 值就好。
第三个操作，由于我们只修改轻链，所以在重链剖分上轻链的数量只有 $\log n$，所以我们暴力跳到每个轻链去修改 $g$ 值即可。
（这也是用重链剖分的原因）

那么这题就做好啦，具体的实现可以看代码。

代码

#include<cmath>
#include<cstdio>
#define uint unsigned intusing 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;
}