题意
给定一棵 $n$ 个点的有根树，其中 $1$ 号点是根，定义 $f(x)=\sum_{i\leq j,\mathrm{LCA}(i,j)=x}(w_i+w_j)$ 。
现在你需要支持两种操作：
1 x v：对于所有 $x$ 子树内和 $x$ 距离不超过 $2$ 的点 $y$ ，令 $w_y\leftarrow w_y+v$ 。
2 x：询问 $f(x)$ 的值。
答案对 $2^{32}$ 取模。
思路
树剖。一个 tip，处理孩子信息时分开计算。
考虑搞掉 $\mathrm{LCA}$ ，设 $S(x)=\sum_{i,j\in \mathrm{subtree}(𝑥),i\leq j}(w_i+w_j)$ ，于是 $f(x)=S(x)−\sum_{y\in \mathrm{son}(x)}S(y)$ 。
$i\leq j$ 和 $i\geq j$ 对称，所以 $2S(𝑥)=\sum_{i,j\in\mathrm{subtree}(𝑥)}(𝑤_𝑖+𝑤_𝑗)+\sum_{i\in\mathrm{subtree}(𝑥)}2𝑤_𝑖$
上式等号右边第一部分可以把 𝑤_𝑖 和 𝑤_𝑗 分开，即得 $2\mathrm{size}(x)\mathrm{sum}(x)$ ，其中 $\mathrm{sum}(𝑥)=\sum_{i\in\mathrm{subtree}(x)}w_i$ 。
于是 $S(x)=(\mathrm{size}(x)+1)\mathrm{sum}(x)$ 。
接下来把 $f(x)$ 分成三部分。
- $S(x)$ ；
- 重儿子 $S(y)$ ；
- 轻儿子 $S(y)$ 之和。
1、2 本质都是求 $\mathrm{sum}$ ，考虑把 $\mathrm{sum}(x)$ 分成“子树初始的权值和子树内的修改”、“父亲的修改”、“父亲的父亲的修改”三部分。第一部分可以直接 dfs 序加树状数组（一次修改 $(y,v)$ 对 $y$ 的祖先的贡献为 $d_2(y)\times y$ ， $d_2(y)$ 为 $y$ 子树内与 $y$ 距离不超过 $2$ 的点数），第二和第三部分可以在每次修改时打标记，每次查询时加上来即可。
接下来求 3。设 $g(x)$ 表示 $x$ 所有轻儿子的 $S(y)$ 之和，需要动态维护 $g(x)$ 。
考虑一次修改 $(x,v)$ 的影响：
- 如果 $y$ 是 $x$ 的子节点，则 $g(x)$ 加上 $ds(y)\times v$ ，其中 $ds(y)$ 为 $y$ 所有轻儿子 $z$ 的 $\mathrm{size}(z)+1$ 的和。
- 如果 $y=x$ ，则 $g(x)$ 加上 $ds_1(x)\times v$ ，其中 $ds_1(x)$ 为 $x$ 所有轻儿子 $y$ 的 $d_1(y)$ （ $y$ 子树内与 $y$ 距离不超过 $1$ 的点数）之和。
- 如果 $(y,z)$ 是 $x$ 到根的路径上的一条边（ $z$ 是 $y$ 轻儿子），则 $g(y)$ 加上 $(\mathrm{size}(z)+1)\times d_2(x)\times v$ ，其中 $d_2(x)$ 为 $x$ 子树内与 $x$ 距离不超过 $2$ 的点数。
对于第 1 个影响，可以在 $x$ 打个标记，当需要使用某个 $g(y)$ 的值时使用 $y$ 父亲的标记即可；而 2、3 影响都可以暴力算。
时间复杂度 $\mathcal{O}((n+Q)\log n)$ 。
const int N = 3e5 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n, q;
int head[N], tot;
struct edge {
int to, nxt;
}e[N];
void Add(int u, int v) {
e[++tot] = (edge) {v, head[u]}, head[u] = tot;
}
int siz[N], fa[N], son[N], dep[N];
ll g[N], wsum[N], w[N], d1[N], d2[N], ds[N], ds1[N];
void dfs1(int u, int fa) {
d1[u] = d2[u] = siz[u] = 1;
wsum[u] = w[u];
dep[u] = dep[fa] + 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
dfs1(v, u);
siz[u] += siz[v];
wsum[u] += wsum[v];
d1[u]++;
d2[u] += d1[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
int dfn[N], idfn[N], top[N], cnt;
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
idfn[dfn[u]] = u;
if (!son[u]) return;
dfs2(son[u], t);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v == son[u]) continue;
dfs2(v, v);
g[u] += wsum[v] * (siz[v] + 1);
ds[u] += siz[v] + 1;
ds1[u] += d1[v] * (siz[v] + 1);
}
}
struct SegmentTree {
struct tree {
int l, r;
ll val, lzy;
} t[N << 2];
void Build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (t[p].l == t[p].r) {
t[p].val = wsum[idfn[l]];
return;
}
int mid = (t[p].l + t[p].r) >> 1;
Build(p << 1, l, mid);
Build(p << 1 | 1, mid + 1, r);
}
void PushDown(int p) {
if (!t[p].lzy)
return;
t[p << 1].lzy += t[p].lzy;
t[p << 1 | 1].lzy += t[p].lzy;
t[p << 1].val += t[p << 1].r - t[p << 1].l + 1 * t[p].lzy;
t[p << 1 | 1].val += (t[p << 1 | 1].r - t[p << 1 | 1].l + 1) * t[p].lzy;
t[p].lzy = 0;
}
void Modify(int p, int l, int r, ll val) {
if (l <= t[p].l && t[p].r <= r) {
t[p].val += (t[p].r - t[p].l + 1) * val;
t[p].lzy += val;
return;
}
PushDown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
Modify(p << 1, l, r, val);
if (r > mid)
Modify(p << 1 | 1, l, r, val);
t[p].val = t[p << 1].val + t[p << 1 | 1].val;
}
ll Query(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].val;
PushDown(p);
int mid = (t[p].l + t[p].r) >> 1, ans = 0;
if (l <= mid)
ans += Query(p << 1, l, r);
if (r > mid)
ans += Query(p << 1 | 1, l, r);
t[p].val = t[p << 1].val + t[p << 1 | 1].val;
return ans;
}
} t;
ll chd[N];
ll getSum(int u) {
if (!u) return 0;
ll ans = t.Query(1, dfn[u], dfn[u]);
ans += chd[fa[u]] * d1[u];
ans += chd[fa[fa[u]]];
return ans * (siz[u] + 1);
}
ll getS(int u) {
ll ans = g[u];
ans += ds[u] * chd[fa[u]];
return ans;
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
n = Read(), q = Read();
for (int i = 2; i <= n; i++) {
fa[i] = Read();
Add(fa[i], i);
}
for(int i = 1; i <= n; i++) w[i] = Read();
dfs1(1, 0);
dfs2(1, 1);
t.Build(1, 1, n);
for (; q--; ) {
int opt = Read(), x = Read();
if (opt == 1) {
ll y = Read();
int now = x;
while (now) {
t.Modify(1, dfn[top[now]], dfn[now], y * d2[x]);
now = fa[top[now]];
}
chd[x] += y;
g[x] += ds1[x] * y;
now = x;
while (now) {
now = top[now];
if (fa[now]) g[fa[now]] += d2[x] * y * (siz[now] + 1);
now = fa[now];
}
} else {
printf ("%u\n", getSum(x) - getSum(son[x]) - getS(x));
}
}
return 0;
}
YbtOJ#705