[COGS 2551] 新型武器

图片加载可能有点慢，请跳过题面先看题解，谢谢

这个题好多解法啊。。。
可以主席树，可以按深度将操作排序离线做
我这里是动态开点线段树，对每一个深度种一棵线段树，下标是节点的$dfs$序
然后这个做法就很简单啊。。。
$
$

//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define inf (1<<30)
#define N (600010)
#define il inline
#define RG register
using namespace std;
il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();
  if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }

int n,m,deep[N],w[N],st[N],ed[N],tim;
int rt[N],sum[N<<2],ls[N<<2],rs[N<<2],cnt;
int num,head[N],nxt[N<<1],to[N<<1];
il void add(int u,int v){
   nxt[++num]=head[u];to[num]=v;head[u]=num;
   nxt[++num]=head[v];to[num]=u;head[v]=num;
}

il void dfs(int x,int f){
   st[x]=++tim;
   deep[x]=deep[f]+1;
   for(int i=head[x];i;i=nxt[i]){
      int v=to[i]; if(v==f) continue;
      dfs(v,x);
   }
   ed[x]=tim;
}

il void update(int &x,int l,int r,int k,int val){
   if(!x) x=++cnt;
   if(l==r){ sum[x]=val; return ; }
   RG int mid=(l+r)>>1;
   if(k<=mid) update(ls[x],l,mid,k,val);
   else update(rs[x],mid+1,r,k,val);
   sum[x]=sum[ls[x]]+sum[rs[x]];
}

il void init(){
   n=gi();
   for(int i=1;i<=n;i++) w[i]=gi();
   for(int i=1;i<n;i++){
      int u=gi(),v=gi();
      add(u,v);
   }
   dfs(1,0);
   for(int i=1;i<=n;i++)
      update(rt[deep[i]],1,n,st[i],w[i]);
}

il int query(int x,int l,int r,int L,int R){
   if(!x) return 0;
   if(L==l && r==R) return sum[x];
   int mid=(l+r)>>1,ret=0;
   if(R<=mid) return query(ls[x],l,mid,L,R);
   else if(L>mid) ret+=query(rs[x],mid+1,r,L,R);
   else return query(ls[x],l,mid,L,mid)+query(rs[x],mid+1,r,mid+1,R);
}

il void work(){
   m=gi();
   while(m--){
      int op=gi(),u=gi(),v=gi();
      if(op==1) update(rt[deep[u]],1,n,st[u],v);
      else{
         if(deep[u]+v>n){ puts("0"); continue; }
         printf("%d\n",query(rt[deep[u]+v],1,n,st[u],ed[u]));
      }
   }
}

int main(){ init(); work(); return 0; }

巴特西

[COGS 2551] 新型武器

最新文章

热门文章