C. Propagating tree（思维 + dfs序 + 线段树）

题目连接
我比较笨，感觉真nm抽象…
分析
参考题解：
没看懂的建议自己老老实实手动模拟一下，雀氏妙！
代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// #include 
#include
#include
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"< PII;
typedef pair PDI;
typedef pair PLL;
typedef pair PDD;
typedef pair > PDID;
typedef pair PCC;
typedef pair > PCII;
typedef pair > PIII;
typedef pair > > PIIII;
typedef pair > PLII;

const int maxn = 2e5 + 7;
const int N = 1e6 + 7;
const int M = 1e6 + 7;
const int mod = 3*5*7*11*13*17*19*23;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int a[maxn];
int pre[maxn],ne[maxn];	//dfs序的第一次出现和最后一次出现
int vis[maxn];	//每个点属于0 1哪一层（节点1属于0层）
vector g[maxn];
int idx;	//dfs序的编号
int n,m;

void dfs(int u,int fa)
{
	pre[u] = ++idx;
	for(auto v : g[u])
	{
		if(v == fa) continue;
		
		vis[v] = vis[u] ^ 1;
		dfs(v,u);
	}
	ne[u] = idx;
}

struct node
{
	int l,r;
	int sum;
	int add;
}tr[2][maxn*4];	//正向，反向线段树

void pushup(int u,int flag)
{
	tr[flag][u].sum = tr[flag][u<<1].sum + tr[flag][u<<1|1].sum;
}

void pushdown(int u,int flag)
{
	if(tr[flag][u].add)
	{
		tr[flag][u<<1].add += tr[flag][u].add;
		tr[flag][u<<1].sum += (tr[flag][u<<1].r - tr[flag][u<<1].l + 1) * tr[flag][u].add;
		
		tr[flag][u<<1|1].add += tr[flag][u].add;
		tr[flag][u<<1|1].sum += (tr[flag][u<<1|1].r - tr[flag][u<<1|1].l + 1) * tr[flag][u].add;
		
		tr[flag][u].add = 0;	
	}
}

void build(int u,int l,int r)
{
	tr[0][u] = {l,r};
	tr[1][u] = {l,r};
	if(l == r) return;
	
	int mid = l + r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	
	pushup(u,0);
	pushup(u,1);
}

void update(int u,int l,int r,int val,int flag)
{
    if(l > r) return;
	if(l <= tr[flag][u].l && tr[flag][u].r <= r)
	{
		tr[flag][u].sum += (tr[flag][u].r - tr[flag][u].l + 1) * val;
		tr[flag][u].add += val;
		
		return;
	}
	
	pushdown(u,flag);	//分裂了，下传懒标记
	
	int mid = tr[flag][u].l + tr[flag][u].r >> 1;
	if(l <= mid) update(u<<1, l, r, val, flag);
	if(r > mid) update(u<<1|1, l, r, val, flag);
	
	pushup(u,flag);	//向上更新
}

ll query(int u,int l,int r,int flag)	//区间查询
{
	if(tr[flag][u].l >= l && tr[flag][u].r <= r) return tr[flag][u].sum;
	
	pushdown(u,flag);	//分裂了，下传懒标记
	
	int mid = tr[flag][u].l + tr[flag][u].r >> 1;
	
	ll sum = 0;
	if(l <= mid) sum += query(u<<1, l, r, flag);
	if(r > mid) sum += query(u<<1|1, l, r, flag);
	
	return sum;
}

int main()
{
	iire(n,m);
	for(int i=1;i<=n;i++) ire(a[i]);
	
	for(int i=1;i
		int a,b;
		iire(a,b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(1,-1);
	
	build(1,1,idx);	//对dfs序建线段树
	
	while(m--)
	{
		int op;
		ire(op);
		
		if(op == 1)	//修改
		{
			int x,y;
			iire(x,y);
			
			int l = pre[x];
			int r = ne[x];
			
 			update(1,l,r,y,vis[x]);
		}
		else
		{
			int x;
			ire(x);
			
			int ans = a[x] + query(1,pre[x],pre[x],vis[x]) - query(1,pre[x],pre[x],vis[x] ^ 1);
			
			cout<
C. Propagating tree（思维 + dfs序 + 线段树）

C/C++/C#相关栏目本月热门文章
