#include<bits/stdc++.h> using namespace std; const int N = 1e6+5; int n, cnt, m, hd[N], c[N], l[N], r[N], d[N], ans[N]; vector<int> q[N]; struct Node{ int to,nxt; }edge[N]; void add(int u, int v){ edge[++cnt].to = v; edge[cnt].nxt = hd[u]; hd[u] = cnt; } void dfs(int u, int dep, int sum) { //自上而下 for(int i = 0; i < q[u].size(); i++) { int j = q[u][i]; //第几个询问 if(r[j] < dep) continue; c[max(dep, l[j])] += d[j]; //c表示层数,这层执行差分 c[r[j]] -= d[j]; } ans[u] = sum + c[dep]; //前缀和 for(int i = hd[u]; i; i = edge[i].nxt) dfs(edge[i].to, dep+1, sum + c[dep]);//如果没有增加,则c[dep]=0 for(int i = 0; i < q[u].size(); i++){ int j = q[u][i]; //第几个询问 if(r[j] < dep) continue; c[max(dep, l[j])] -= d[j]; c[r[j]] += d[j]; } } int main() { scanf("%d",&n); int x, p = 0; for(int i = 2; i <= n; i++) { scanf("%d",&x); add(x,i);//单向边 } scanf("%d",&m); for(int i = 1; i <= m; i++) { scanf("%d%d%d%d", &x, &l[i], &r[i], &d[i]); q[x].push_back(i); //这个子树对应的第几个询问 } dfs(1,1,0); for(int i = 1; i <= n; i++) p = (p * 12347 + ans[i]) % 1000000007; printf("%d\n",p); return 0; }
标签:cnt,int,询问,dep,edge,树上,sum,hd From: https://www.cnblogs.com/caterpillor/p/17625272.html