LibreOJ-dfs序2 (dfs序,线段树)

Nova ·
更新时间:2024-11-10
· 562 次阅读

LibreOJ-dfs序2 (dfs序,线段树) 题目描述

给一棵有根树,这棵树由编号为1~N 的 N个结点组成。根结点的编号为R。每个结点都有一个权值,结点 的权值为 。 接下来有 M组操作,操作分为两类:

1 a x,表示将结点 的子树上所有结点的权值增加 ;
2 a,表示求结点 的子树上所有结点的权值之和。

输入格式

第一行有三个整数 N,M和R。
第二行有 N个整数,第 i个整数表示 vi
在接下来的 N-1行中,每行两个整数,表示一条边。
在接下来的 M行中,每行一组操作。

输出格式

对于每组 2 a操作,输出一个整数,表示「以结点 a为根的子树」上所有结点的权值之和。

用到了dfs序,两个数组 st[ ] ,en[ ] 储存每个点遍历的出入时间,通过时间可算出子树节点。
通过 mp[ ] 数组,找到结点与树的对应(映射)
线段树的区间修改和区间查询,并结合 st[ ] , en[ ] 数组,找到所用的区间。

区间修改时标记 lazy[ ] 数组,查询时再向下传递。

代码↓

#include using namespace std; const int N = 1e6 + 5; vector q[N]; int st[N],en[N],tmp=0; int n,m,r,b[N]; long long sum[N<<2],lazy[N<<2]; int mp[N]; void dfs(int u, int fa) { st[u]=++tmp; mp[tmp] = u; for(auto v:q[u]) { if(v==fa) continue; dfs(v,u); } en[u]=tmp; } int a[1005],c[1005]; void pushup(int i) { sum[i]=sum[i<<1]+sum[i<<1|1]; } void up(int i,long long len,long long v) { sum[i]+=len * v; lazy[i]+=v; } void pushdown(int i,int l,int r) { int mid=(l+r)/2; if(lazy[i]) { up(i<<1,mid-l+1,lazy[i]); up(i<<1|1,r-mid,lazy[i]); lazy[i] = 0; } } void build(int i,int l,int r) { if(l==r) { sum[i] = b[mp[l]]; return ; } int mid=(l+r)/2; build(i<<1,l,mid); build(i<<1|1,mid+1,r); pushup(i); } //区间修改 void zeng(int i,int ql,int qr,int l,int r,int v) { if(ql=r) { up(i,r-l+1,v); return ; } int mid=(l+r)/2; pushdown(i,l,r); if(ql<=mid) zeng(i<mid) zeng(i<<1|1,ql,qr,mid+1,r,v); pushup(i); } //区间查询 long long he(int i,int ql,int qr,int l,int r) { if(ql=r) { return sum[i]; } int mid=(l+r)/2; pushdown(i,l,r); long long ans = 0; if(ql<=mid) ans+=he(i<mid) ans+=he(i<>n>>m>>r; for(int i=1;i>b[i]; } int x,y; for(int i=1;i>x>>y; q[x].push_back(y); q[y].push_back(x); } dfs(r,0); // dfs序 build(1, 1, n); int f; while(m--) { cin>>f; if(f==1) { cin>>x>>y; // st[x], en[x]可找到子树的区间 zeng(1, st[x], en[x], 1, n, y); } else { cin>>x; cout<<he(1,st[x],en[x],1,n)<<endl; } } return 0; } 师子墨么么么么么么 原创文章 1获赞 1访问量 43 关注 私信 展开阅读全文
作者:师子墨么么么么么么



线段树 dfs

需要 登录 后方可回复, 如果你还没有账号请 注册新账号