本主题开始看到以为段树或树状数组，但是，对于一个节点的有疑问的所有子节点的加权，这一条件被视为树的根，像 然后1号是肯定在第一层中，然后建立一个单向侧倒查，然后记录下来 其中每个节点 层，终于 两个节点 之间的差 图层知道，上easy加权成交，然后，我们开始建立的数组，一直爆错，后来发现 是范围有问题，这样直接建立是错的，由于不知道详细范围，数字太大了。 所以參考了一下
厉害啊。我想不到。原来能够建立两个树状数组，然后 在深搜找出节点所在层的同一时候 也记录一下 它的时间戳，也就是这个节点第一次被訪问到的作为一个记录和的树状数组下标。以及往下找子节点回溯回来的这个时间错 建立还有一个记录要减去的和的树状数组下标，这样范围就确定了，可是这样无法直接加权，要对 第一次訪问到的 加权 然后对 回溯的 进行相同的值的 负值加权，同一时候加权的时候 直接所有都加上去。不考虑节点与此时父节点相差层数，仅仅考虑与根的，然后 这样是多加了的。这时候 能够把要减去的 给算好，最后一起减去就能够了，要减去的 就直接加上 k，最后一起算的时候 再乘上与根 相差层数，两个树状数组都以与主根 相差层数为基准。这样 就能够了
然后这个取余不知道怎么了。一直WA，后来我手写了一个 MODE函数才过，原来直接取模 我也考虑了负数 要多加一个MOD可是 还是WA，为什么别人能够 我就不行了 郁闷
#define MOD 1000000007int n,tot;int vis[300000 + 55];int le[300000 + 55],ri[300000 + 55];ll ad[300000 + 55],sub[300000 + 55];vector G[300000 + 55];void init() { for(int i=0;i<300000 + 55;i++)G[i].clear(); memset(vis,0,sizeof(vis)); memset(ad,0,sizeof(ad)); memset(sub,0,sizeof(sub)); memset(le,0,sizeof(le)); memset(ri,0,sizeof(ri)); tot = 0;}bool input() { while(cin>>n) { for(int i=2;i<=n;i++) { int x; scanf("%d",&x); G[x].push_back(i); } return false; } return true;}void dfs(int u,int cnt) { tot++; le[u] = tot; for(int i=0;i = MOD)x %= MOD; else if(x < 0ll)x = (x + MOD)%MOD; return x;}int lowbit(int x) { return x&(-x);}void add1(int i, ll val) { while (i <= tot) { ad[i] += val; ad[i] = MODE(ad[i]); i += lowbit(i); }}void add2(int i,ll val) { while(i <= tot) { sub[i] += val; sub[i] = MODE(sub[i]); i += lowbit(i); }}ll get_sum1(int i) { ll sum = 0; while (i > 0) { sum += ad[i]; sum = MODE(sum); i -= lowbit(i); } return sum;}ll get_sum2(int i) { ll sum = 0ll; while(i > 0) { sum += sub[i]; sum = MODE(sum); i -= lowbit(i); } return sum;}void cal() { dfs(1,0); int q; cin>>q; while(q--) { int type; scanf("%d",&type); if(type == 1) { int v; ll x,k; scanf("%d %I64d %I64d",&v,&x,&k); x = (x + (vis[v] - 1) * k)%MOD; add1(le[v],x); add1(ri[v] + 1,-x); add2(le[v],k); add2(ri[v] + 1,-k); } else { int v; scanf("%d",&v); ll xx = get_sum1(le[v]); ll yy = get_sum2(le[v]); ll ans = MODE(xx - MODE((vis[v] - 1) * yy)); printf("%I64d\n",ans); } }}void output() {}int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0;} 版权声明：本文博客原创文章。博客，未经同意，不得转载。