NC23051 华华和月月种树(树剖+离线)

华华和月月种树

https://ac.nowcoder.com/acm/problem/23051

题目链接


题意:
初始有一零结点,权值为0,根据相应操作维护这棵动态有根树。
操作 1:输入格式 1 i ,表示使节点 i 长出了一个新的儿子节点,权值为0,编号为当前最大编号 +1。
操作 2:输入格式 2 i a ,表示使节点 i 的子树中所有节点(即它和它的所有子孙节点)权值加 a 。
操作 3:输入格式 3 i,输出节点i权值。


题解:
因为树的结点是动态变化的,无法在线维护,先求出总连接情况,然后考虑用特殊方法维护结点值。
对于固定连接情况的树,其权值情况可通过树链剖分维护出来。
通过结点加入的先后顺序关系,容易想到在一结点诞生时记录其权值,待询问时求出此时权值再减去诞生时权值即为该结点的真正权值。


代码如下:

#include<bits/stdc++.h>
#define len (r-l+1)
#define ls p<<1,l,mid
#define rs p<<1|1,mid+1,r
using namespace std;
const int nx=1e5+5;
int h[nx],to[nx<<1],nxt[nx<<1],cnt;
int a[nx<<2],laz[nx<<2];
int son[nx],id[nx],fa[nx],dep[nx],siz[nx],top[nx],df;
struct node{
    int a,b,c;
}s[nx<<2];
inline void add(int u,int v){
    to[++cnt]=v,nxt[cnt]=h[u],h[u]=cnt;
    to[++cnt]=u,nxt[cnt]=h[v],h[v]=cnt;
}
inline void read(int &x){
    x=0;char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c&15);
}
void pushdown(int p,int tot){
    laz[p<<1]+=laz[p],laz[p<<1|1]+=laz[p];
    a[p<<1]=a[p<<1]+laz[p]*(tot-tot/2);
    a[p<<1|1]=a[p<<1|1]+tot/2*laz[p];
    laz[p]=0;
}
void up(int p,int l,int r,int x,int y,int z){
    if(x<=l&&r<=y){
        laz[p]+=z,a[p]=a[p]+z*len;
        return;
    }
    if(laz[p])pushdown(p,len);
    int mid=(l+r)>>1;
    if(x<=mid)up(ls,x,y,z);
    if(mid<y)up(rs,x,y,z);
    a[p]=a[p<<1]+a[p<<1|1];
}
int get(int p,int l,int r,int x){
    if(l==r)return a[p];
    if(laz[p])pushdown(p,len);
    int mid=l+r>>1;
    if(x<=mid)return get(ls,x);
    return get(rs,x);
}
void dfs1(int x,int f,int deep){
    dep[x]=deep,fa[x]=f,siz[x]=1;
    int mx=-1,y;
    for(int i=h[x];i;i=nxt[i]){
        y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>mx)mx=siz[y],son[x]=y;
    }
}
void dfs2(int x,int gf){
    id[x]=++df,top[x]=gf;
    if(!son[x])return;
    dfs2(son[x],gf);
    for(int i=h[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
int val[nx];
int main(){
    int n,op,i,d,now=0;
    read(n);
    for(int j=0;j<n;++j){
        read(op),read(i);
        if(op==1)add(++now,i),s[j]={1,i,now};
        else if(op==2)read(d),s[j]={2,i,d};
        else s[j]={3,i,0};
    }
    dfs1(0,-1,1),dfs2(0,0);
    ++now;//含零总结点数 
    for(int j=0;j<n;++j){
        op=s[j].a,i=s[j].b,d=s[j].c;
        if(op==1)val[d]=get(1,1,now,id[d]);
        else if(op==2)up(1,1,now,id[i],id[i]+siz[i]-1,d);
        else printf("%d\n",get(1,1,now,id[i])-val[i]);
    }
}
全部评论

相关推荐

01-26 18:45
门头沟学院 Java
一天代码十万三:哥们实习再包一下吧,产出太笼统了,尽量体现业务
点赞 评论 收藏
分享
双飞二本嵌入式求拷打我是在&nbsp;BOSS&nbsp;上投递的简历,好多都没人回复,这是开场白和简历求大神帮忙看看。您好!我是2025届应届生,最快可在一周内上岗,能够实习六个月以上,并接受加班。以下是我的核心优势和相关经验:1.&nbsp;嵌入式开发能力:&nbsp;&nbsp;&nbsp;熟练掌握STM32系列单片机及其外设(如GPIO、定时器、ADC、DAC、I2C、SPI、UART等),能够独立完成硬件驱动开发和调试。&nbsp;&nbsp;熟悉FreeRTOS实时操作系统,具备多任务调度和资源管理经验。&nbsp;&nbsp;熟悉LVGL图形库开发,能够实现嵌入式设备的图形界面设计。2.&nbsp;硬件设计能力:&nbsp;&nbsp;&nbsp;具备PCB设计经验,曾为2023年工创赛物流搬运赛道设计小车主板,带领团队获得国家级银奖。&nbsp;&nbsp;&nbsp;熟悉硬件原理图分析,能够快速理解并调试硬件电路。3.&nbsp;机器人开发与竞赛经验:&nbsp;&nbsp;&nbsp;在全国大学生智能车竞赛、ROS机器人竞赛中多次获得国家级奖项,具备丰富的机器人开发经验。&nbsp;&nbsp;&nbsp;熟悉Linux环境,对ROS和ROS&nbsp;2有一定了解,能够进行机器人系统的开发与调试。4.&nbsp;编程能力:&nbsp;&nbsp;&nbsp;熟悉C/C++,熟悉Python,能够高效完成嵌入式开发和算法实现。&nbsp;&nbsp;&nbsp;具备良好的代码规范和文档编写能力。5.&nbsp;团队协作与领导能力:&nbsp;&nbsp;&nbsp;在多个项目中担任核心开发或团队负责人,具备良好的沟通能力和团队协作精神。&nbsp;&nbsp;&nbsp;在工创赛中带领团队完成项目规划、任务分配和技术攻关,展现了较强的领导力。我对嵌入式开发、机器人技术和智能硬件充满热情,期待加入贵公司,与团队共同成长,为公司创造价值!如果有合适的岗位,欢迎随时联系我,期待进一步沟通!
沉淀一会:嵌入式就是狗屎
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务