首页 > 其他分享 >树上询问

树上询问

时间:2023-08-12 19:00:34浏览次数:32  
标签:cnt int 询问 dep edge 树上 sum hd

#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

相关文章

  • L33_用日语询问需要等候多长时间
    语料地址概述在日语中,询问所需的时间,长度和距离或者数量的时候,可以采用疑问词:どのくらい,比如:どのくらいかかりますか需要多长时间?どのくらい待ちますか需要等候多长时间?动画会话どのくらい待ちますか要等多长时间?15分くらいです15分钟左右わかりました......
  • 树上问题记录
    记录一下这一类问题。T1P4211[LNOI2014]LCA每次给出\(l,r,x\),定义\(dep_u\)为\(u\)节点到根节点的距离+1,求$\sum_{i=l}^rdep(lca(i,z))$。\(n\)个节点,\(m\)次询问,其中\(n,m\leq5e4\)。题目很简洁,我们如果暴力求每一个lca,复杂度将是\(O(n^2\logn)......
  • 【W的AC企划 - 第六期】树上分治
    往期浏览树上分治点分治讲解每次选取树的重心进行递归分治,中阶算法,大部分模板不需要理解,但是每一题都需要对维护函数进行修改。复杂度\(\mathcalO(N\logN)\)。个人封装由于需要进行一定程度的修改,不符合结构体封装的原则,故没有使用结构体。introot=0,MaxTree=1e1......
  • 树上计数2
    [树上计数2](2534.树上计数2-AcWing题库)我们先考虑一般的问题,即序列上的问题。发现这题是HH的项链。然后我们考虑树上怎么转换成序列上。我们使用欧拉序(对于每个点,在进入和离开时各记录一次,类比dfs序)。对于点\(u\),令\(fi_u,ls_u\)表示进入/出去的时间戳。如图(样例)......
  • 树上数据结构
    树上问题树链剖分学习笔记重链剖分对树进行重链优先搜索,暴力求一条路径的复杂度为logn模板voidtree_build(intu,intfa){//重链优先搜索 siz[u]=1; f[u]=fa; hson[u]=0; for(auto&v:adj[u]){deep[v]=deep[u]+1; if(v==fa)continue; tree_build(v,u);......
  • 前端学习笔记202305学习笔记第二十一天-vue3.0-使用messagebox组件询问用户是否可以删
       ......
  • 前端学习笔记202305学习笔记第二十一天-vue3.0-使用messagebox组件询问删除用户功能
      ......
  • 2023-08-02:给定一棵树,一共有n个点, 每个点上没有值,请把1~n这些数字,不重复的分配到二叉
    2023-08-02:给定一棵树,一共有n个点,每个点上没有值,请把1~n这些数字,不重复的分配到二叉树上,做到:奇数层节点的值总和与偶数层节点的值总和相差不超过1。返回奇数层节点分配值的一个方案。2<=n<=10^5。来自腾讯音乐。答案2023-08-02:大致步骤如下:1.计算出1到n的总和s......
  • 2023-08-02:给定一棵树,一共有n个点, 每个点上没有值,请把1~n这些数字,不重复的分配到二叉
    2023-08-02:给定一棵树,一共有n个点,每个点上没有值,请把1~n这些数字,不重复的分配到二叉树上,做到:奇数层节点的值总和与偶数层节点的值总和相差不超过1。返回奇数层节点分配值的一个方案。2<=n<=10^5。来自腾讯音乐。答案2023-08-02:大致步骤如下:1.计算出1到n的总和sum。2.确......
  • 数列询问
    题目描述有一个长度为n的数列,数列中每个数都是[0,p-1]之间的整数。小明不知道数列中每个数的值,所以向小红做了m次询问。每次小明会向小红询问一个区间[l,r] 中所有数的和对p取模的结果。问完所有问题后,小明发现小红的回答中似乎存在矛盾。现在小明想找到最大的X,满足小......