树上询问

Jeanny / 2023-08-12 / 原文

#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;
}