首页 > 其他分享 >E 华华和月月种树 添加子节点并给子树加权值 树状数组+dfs序+离线操作

E 华华和月月种树 添加子节点并给子树加权值 树状数组+dfs序+离线操作

时间:2022-08-29 00:25:38浏览次数:93  
标签:华华 int 离线 pos dfs 权值 操作 节点

 链接:https://ac.nowcoder.com/acm/problem/23051
来源:牛客网

题目描述

华华看书了解到,一起玩养成类的游戏有助于两人培养感情。所以他决定和月月一起种一棵树。因为华华现在也是信息学高手了,所以他们种的树是信息学意义下的。
华华和月月一起维护了一棵动态有根树,每个点有一个权值。刚开存档的时候,树上只有 0 号节点,权值为 0 。接下来有两种操作:
操作 1:输入格式1 i1\ i1 i,表示月月氪金使节点 i 长出了一个新的儿子节点,权值为0,编号为当前最大编号 +1(也可以理解为,当前是第几个操作 1,新节点的编号就是多少)。
操作 2:输入格式 2 i a2 \ i \ a2 i a,表示华华上线做任务使节点 i 的子树中所有节点(即它和它的所有子孙节点)权值加 a 。
但是月月有时会检查华华有没有认真维护这棵树,会作出询问:
询问 3:输入格式3 i3\ i3 i,华华需要给出 i 节点此时的权值。
华华当然有认真种树了,不过还是希望能写个程序以备不时之需。

输入描述:

第一行一个正整数M,接下来M行,每行先输入一个正整数O表示操作类型,再输入一个非负整数i表示操作或询问的节点编号,如果O=2,再输入一个正整数a。

输出描述:

对于每个询问3,输出一个非负整数表示询问的答案。
示例1

输入

复制
9
1 0
2 0 1
3 0
3 1
1 0
1 1
2 0 2
3 1
3 3

输出

复制
1
1
3
2

备注:

1≤M≤4×1051\le M\le 4\times 10^51≤M≤4×105,保证操作1的数量不超过10510^5105,保证操作2中的参数a满足1≤a≤9991\le a\le 9991≤a≤999

分析

题意:

操作1:给节点 i 新加一个节点,编号为总结点数

操作2:给节点 i 和它的子树上的每一个节点 增加一个权值 w

操作3:查询节点 i 的权值

操作2 + 操作3 可以用 dfs序 + 树状数组来解决

操作1,考虑离线操作,将所有节点保存下来,最后再跑dfs序

当枚举到操作 1 的时候,给这个点的编号位置加上这个点刚加过的权值,最后查询的时候把这个权值删除就可以了

 

//-------------------------代码----------------------------

//#define int ll
const int N = 4e5+10;
int n,m;

V<int> e[N];
int l[N],r[N],num,op[N],pos[N],a[N],w[N];

void dfs(int u,int fa) {
    l[u] = ++ num;
    for(auto it:e[u]) {
        if(it == fa) continue;
        dfs(it,u);
    }
    r[u] = num;
}

int tr[N<<2];
void add(int x,int v) {
    for(int i = x;i<=num + 1;i += lowbit(i) ) tr[i] += v;
}
int sum(int x) {
    int res = 0;for(int i = x;i;i-=lowbit(i)) res += tr[i];return res;
}


void solve()
{
//    cin>>n>>m;
    cin>>m;
    int cnt = 0;
    fo(i,1,m) {
        cin>>op[i];cin>>pos[i];
        if(op[i] == 2) cin>>a[i];
        else if(op[i] == 1) {
            e[pos[i]].pb(++cnt);
            e[cnt].pb(pos[i]);
            a[i] = cnt;
        }
    }
    dfs(0, -1);    
    ms(tr,0);
    fo(i,1,m) {
        if(op[i] == 1) {
            w[l[a[i]]] = sum(l[a[i]]);
        } else if(op[i] == 2) {
            add(l[pos[i]],a[i]);
            add(r[pos[i]] + 1,-a[i]);
        } else {
            int ans = sum(l[pos[i]]) - w[l[pos[i]]];
            cout<<ans<<endl;
        }
    }
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

标签:华华,int,离线,pos,dfs,权值,操作,节点
From: https://www.cnblogs.com/er007/p/16634531.html

相关文章

  • 5.Springboot离线新建环境
    1.新建Maven项目2.pom文件导入org.springframework.bootspring-boot-starter-parent2.7.2org.springframework.bootspring-boot-starter-web<dependency>......
  • ecs离线方式安装ansilbe的rpm包
    1.安装包下载文章背景:因为ecs机器没有连接外网,同时需要安装ansilbe,这时就需要从其他机器将包下载到本地。系统:AlibabaCloudLinux2.1903LTS64位软件包名版本......
  • 启动HDFS伪分布式环境时报权限错误
    问题描述操作系统:Ubuntu18.04LTSHDFS版本:hadoop-3.2.3普通用户登录,参照官方文档在单机上安装伪分布式环境时,启动HDFS报权限错误。具体报错信息如下:$./sbin/start-df......
  • visual studio 2022离线安装包制作教程
    1、在线下载VisualStudi安装包https://aka.ms/vs/17/release/vs_enterprise.exe  2、在线安装visualsudio22布局 2.1.NETWeb和.NET桌面开发,运行(不选en-US......
  • 2022-8-27 每日一题-层序遍历+标记+剑指offer-字典树+dfs
    662.二叉树最大宽度难度中等409收藏分享切换为英文接收动态反馈给你一棵二叉树的根节点 root ,返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度......
  • iGG离线安装器
    安装器下载地址:iGG学术助手官网https://iguge.xyz/ 第一步:下载并解压缩本插件    第二步:打开Google浏览器(Chrome)在地址输入chrome://extensions/或者:点......
  • VSCODE离线配置远程开发环境
    1.下载VSCODE插件VSCODE的插件和VSCODE的版本是对应的,为了下载到兼容的版本,首先查看VSCODE的版本。帮助---》关于从上图中可以看到VSCODE的版本和日期,下载的插件只要时......
  • bfs和dfs基础
    #bfs&dfsgraph={"A":["B","C"],"B":["A","C","D"],"C":["A","B","D","E"],"D":["B","......
  • 【HDFS】一次Namenode的RPC延迟故障排查引发的深入思考
    一次Namenode的RPC延迟故障排查引发的深入思考前言正文问题排查初步定位临时恢复定位可疑进程问题分析问题脚本分析问题原因分析代码分析测试代码prometheus_clien......
  • LCA C 求和 求子树权值和 树上节点单点修改 dfs序+树状数组
     链接:https://ac.nowcoder.com/acm/problem/204871来源:牛客网题目描述已知有 nnn个节点,有 n−1n-1n−1条边,形成一个树的结构。给......