[题解]CF383C Propagating tree

发表于 | 评论数： | 阅读次数：
本文字数： 2.4k | 阅读时长 ≈ 2 分钟

题目描述

洛谷

CF

题解

题目要求对给定的$u$节点的子树进行操作，使其$0$级节点加上$val$，$1$级节点减去$val$，$2$级节点加上$val$，以此类推。

由于对子树进行操作，考虑节点的$dfs$序，计算每个节点第一次被访问和回溯时的时间戳，则它的子树$dfs$序都在这段区间内，由此将树上修改转化为区间修改。

观察到一个节点加上或减去$val$与其深度的奇偶性有关，假定根节点深度为$1$。我们在以深度为奇数的节点的子树修改时令整个区间加上$val$，深度为偶数的节点的子树修改时令整个区间加上$-val$，输出时奇数深度的节点加上修改的值，偶数深度的节点减去修改的值即可解决。

由于题目要求区间修改单点查询，可以用树状数组解决。注意初始值不受影响。所以不需要进行初始化(注释部分)，在输出时加上初始值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;

int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}

int n , m;
int Black[MAXN] , White[MAXN] , ti;
int head[MAXN] , cnt , val[MAXN] , depth[MAXN];
int tree[MAXN] , id[MAXN];
struct G{
	int To , Nxt;
}edge[MAXN << 1];
void add(int From , int To)
{
	edge[++ cnt].Nxt = head[From];
	edge[cnt].To = To;
	head[From] = cnt;
}
void dfs(int k , int fa)
{
	depth[k] = depth[fa] + 1;
	Black[k] = ++ ti;
	id[ti] = k;
	for(int i = head[k]; i; i = edge[i].Nxt)
	{
		int v = edge[i].To;
		if(v == fa) continue;
		dfs(v , k);
	}
	White[k] = ti;
}
int lowbit(int x)
{
	return x & -x;
} 
void Add(int pos, int w)
{
	while(pos <= n) tree[pos] += w , pos += lowbit(pos);
}
int query(int pos)
{
	int sum = 0;
	while(pos) sum += tree[pos] , pos -= lowbit(pos);
	return sum;
}
int main()
{
	n = read() , m = read();
	for(int i = 1; i <= n; i ++) val[i] = read();
	for(int i = 1; i < n; i ++)
	{
		int u = read() , v = read();
		add(u , v) , add(v , u);
	}
	dfs(1 , 0);
//	for(int i = 2; i <= n; i ++)
//	{
//		Add(i , val[id[i]] - val[id[i - 1]]);
//	}
	while(m --)
	{
		int op = read();
		if(op == 1)
		{
			int x = read() , val = read();
			if(depth[x] % 2 == 1)
			  Add(Black[x] , val) , Add(White[x] + 1 , -val);
			else 
			  Add(Black[x] , -val) , Add(White[x] + 1 , val);
		}
		else
		{
			int x = read();
			int s = query(Black[x]);
			if(depth[x] % 2 == 1)
			  printf("%d\n" , val[x] + s);
			else 
			  printf("%d\n" , val[x] - s);
		}
	}
	return 0;
}