题意略。
思路：
将树上的节点编好dfs序，然后就可以用树状数组区间修改点查询了。
我们用 lft[v] 和 rht[v]来表示v的子树在dfs序中的左端和右端，这样才方便我们对树状数组的操作。
其实这个题目的问题在于每个点在修改时，修改的值不是一定的，会发生变化。
我是将加上的值和减去的值分开了。
开两个树状数组，一个记录加：在我们进行加操作的时候，加上的值是x + deep[v] * k。
一个记录减：在我们进行减操作的时候，减去的值就是k。
最后在获取答案的时候，ans = sum(v,0) - deep[v] * sum(v,1)。
详见代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 3e5 + 5; const LL mod = 1e9 + 7; int lft[maxn],rht[maxn],n,q,cnt; LL deep[maxn],BIT[2][maxn]; vector<int> graph[maxn]; void dfs(int cur,int d){ lft[cur] = ++cnt; deep[cur] = d; for(int i = 0;i < graph[cur].size();++i){ int v = graph[cur][i]; dfs(v,d + 1); } rht[cur] = cnt; } int lowbit(int k){ return (k & -k); } void add(int pos,LL val,int idx){ while(pos <= n){ BIT[idx][pos] += val; BIT[idx][pos] %= mod; pos += lowbit(pos); } } LL sum(int pos,int idx){ LL ret = 0; while(pos > 0){ ret += BIT[idx][pos]; pos -= lowbit(pos); ret %= mod; } return ret; } int main(){ scanf("%d",&n); int pi; for(int i = 2;i <= n;++i){ scanf("%d",&pi); graph[pi].push_back(i); } dfs(1,1); scanf("%d",&q); for(int i = 0;i < q;++i){ int type; scanf("%d",&type); if(type == 1){ int v; LL x,k; scanf("%d%lld%lld",&v,&x,&k); LL val = (x + deep[v] * k) % mod; add(lft[v],val,0); add(rht[v] + 1,-val,0); add(lft[v],k,1); add(rht[v] + 1,-k,1); } else{ int v; scanf("%d",&v); int pos = lft[v]; LL part1 = sum(pos,0); LL part2 = sum(pos,1); part2 = part2 * deep[v] % mod; LL ans = ((part1 - part2) % mod + mod) % mod; printf("%lld\n",ans); } } return 0; }
原文：https://www.cnblogs.com/tiberius/p/9409445.html