LibreOJ-dfs序2 (dfs序，线段树）

Nova ·

更新时间:2024-11-13

· 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;
}