Codeforces Round #225 (Div. 1) C tree array || segment tree_html/css_WEB-ITnose

I am very happy to see this question. I have the impression that it is very similar to what I have done before. It seems that I have done one recently, using timestamps as intervals to build a tree array. Then at first I thought the question meant, give x If you add val to a point, -val will be added to all nodes below it; so at the beginning, two tree arrays were established by adding and subtracting, and finally subtracting is the answer. After writing it, I found that it does not match the case. After reading the question, I didn’t find that I read it wrong. I misunderstood that sentence. Then I read this:
http://blog.csdn.net/keshuai19940722/article/details/18967661
Look carefully at the processing part. I I thought there were rules for dividing parity, but later I found out that I had read the question wrong. It turned out to be x point plus val, the child nodes directly connected to it plus -val, and the child nodes of its child nodes plus val. analogy. . . Ha ha. . Cry

The method is the same as the previous question. For this tree, perform dfs, and record the relationship between the distance and the current layer number, expressed as odd and even numbers, and then use the timestamp of each node being dfs Establish an interval to map the tree array to it, and finally separate the odd and even numbers. The additions are in one tree array, and the subtractions are in another. Then when the single point value is finally calculated, it is the distance between the point and the root node. That is, the value that should be added by itself is subtracted from the corresponding value that should be subtracted from another tree array. Then, the value of each node itself is not added to the tree array at the beginning, and the original value must be added. has a value, this is the answer

Then I did it with a line segment tree, also using the timestamp, and recording the parity of this node from the root, and then also established two line segment trees, one record Odd number processing, one record even number processing, but I don’t know where I wrote it wrong. I revised it for a long time, but when it didn’t work, I wrote it again. I really forgot what I learned. . .

For tree array:

int n;int m;int c[2][200000 * 2 + 55];typedef struct Node {	int l,r,val;	int now;};Node node[200000 + 55];vector<int > G[200000 + 55];int cnt;void init() {	memset(c,0,sizeof(c));	for(int i=0;i<200000 + 55;i++)G[i].clear();}bool input() {	while(cin>>n>>m) {		for(int i=1;i<=n;i++)cin>>node[i].val;		int tmp = n - 1;		while(tmp--) {			int u,v;			scanf("%d %d",&u,&v);			G[u].push_back(v);			G[v].push_back(u);		}		return false;	}	return true;}int lowbit(int x) {	return x&(-x);}void add(int i,int val,int *aa) {	while(i <= 2 * n) {		aa[i] += val;		i += lowbit(i);	}}int get_sum(int i,int *aa) {	int sum = 0;	while(i > 0) {		sum += aa[i];		i -= lowbit(i);	}	return sum;}void dfs(int u,int pre,int tot) {	node[u].l = cnt++;	node[u].now = tot;	for(int i=0;i<G[u].size();i++) {		int v = G[u][i];		if(v == pre)continue;		dfs(v,u,tot^1);	}	node[u].r = cnt++;}void cal() {	cnt = 1;	dfs(1,-1,0);	while(m--) {		int type;		cin>>type;		if(type == 1) {			int x,y;			cin>>x>>y;			//int tmp = node[x].now;			//int aa = node[x].l;			//int bb = node[x].r;			add(node[x].l,y,c[node[x].now]);			add(node[x].r + 1,-y,c[node[x].now]);		}		else {			int x;			cin>>x;			//int aa = (get_sum(node[x].l,c[node[x].d]) /*- get_sum(node[x].l - 1,c[node[x].d])*/);			//int bb = (get_sum(node[x].l,c[node[x].d^1])/* - get_sum(node[x].l - 1,c[node[x].d^1])*/);			//int cc = 0;			int ans = get_sum(node[x].l,c[node[x].now]) - get_sum(node[x].l,c[node[x].now^1]);			ans += node[x].val;			cout<<ans<<endl;		}	}}void output() {}int main() {	while(true) {		init();		if(input())return 0;		cal();		output();	}	return 0;}

For line segment tree:

const int N = 200000 + 55;int n;int m;int nnum[N + 55];int le[N + 55],ri[N + 55],belong[N + 55];int head[N + 55];typedef struct Node {	int l,r;	ll sum;	int lazy;};Node tree_even[N * 4 + 55],tree_odd[N * 4 + 55];typedef struct NODE {	int fro,to;	int nex;};NODE edge[2 * N + 55];int tot;int cnt;void add(int u,int v) {	edge[tot].fro = u;	edge[tot].to = v;	edge[tot].nex = head[u];	head[u] = tot++;}void dfs(int u,int pre,int d) {	le[u] = ++cnt;	for(int i=head[u];i!=-1;i=edge[i].nex) {		int v = edge[i].to;		if(v == pre)continue;		dfs(v,u,d^1);	}	belong[le[u]] = d;	ri[le[u]] = cnt;}void push_up(int id,Node *tree) {	tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;}void push_down(int id,Node *tree) {	if(tree[id].lazy == 0)return ;	tree[id].sum += (tree[id].r - tree[id].l + 1) * tree[id].lazy;	if(tree[id].l == tree[id].r) {		tree[id].lazy = 0;		return ;	}	tree[id<<1].lazy += tree[id].lazy;	tree[id<<1|1].lazy += tree[id].lazy;	tree[id].lazy = 0;}void build(int l,int r,int id,Node *tree) {	tree[id].l = l;	tree[id].r = r;	tree[id].lazy = 0;	if(l == r) {		tree[id].sum = 0ll;		return ;	}	int mid = (l + r)>>1;	build(l,mid,id<<1,tree);	build(mid + 1,r,id<<1|1,tree);	push_up(id,tree);}void update(int l,int r,int id,ll val,Node *tree) {	if(tree[id].l == l && tree[id].r == r) {		tree[id].lazy += val;		push_down(id,tree);		return ;	}	push_down(id,tree);	int mid = (tree[id].l + tree[id].r)>>1;	if(r <= mid)update(l,r,id<<1,val,tree);	else if(l > mid)update(l,r,id<<1|1,val,tree);	else {		update(l,mid,id<<1,val,tree);		update(mid + 1,r,id<<1|1,val,tree);	}	push_up(id,tree);}ll query(int l,int r,int id,Node *tree) {	if(tree[id].l == l && tree[id].r == r) {		push_down(id,tree);		return tree[id].sum;	}	push_down(id,tree);	int mid = (tree[id].l + tree[id].r)>>1;	ll ret = 0ll;	if(r <= mid)ret += query(l,r,id<<1,tree);	else if(l > mid)ret += query(l,r,id<<1|1,tree);	else {		ret += query(l,mid,id<<1,tree);		ret += query(mid + 1,r,id<<1|1,tree);	}	return ret;}void init() {	memset(tree_even,0,sizeof(tree_even));	memset(tree_odd,0,sizeof(tree_odd));	memset(head,-1,sizeof(head));	tot = 1;	cnt = 0;}bool input() {	while(cin>>n>>m) {		for(int i=1;i<=n;i++)cin>>nnum[i];		for(int i=1;i<n;i++) {			int u,v;			cin>>u>>v;			add(u,v);			add(v,u);		}		return false;	}	return true;}void cal() {	dfs(1,-1,1);	build(1,n,1,tree_even);	build(1,n,1,tree_odd);	while(m--) {		int type;		cin>>type;		if(type == 1) {			int x,y;			cin>>x>>y;			int left = le[x];			int right = ri[left];			if(belong[left]&1) update(left,right,1,y,tree_odd);			else update(left,right,1,y,tree_even);		}		else {			int x;			cin>>x;			int left = le[x];			ll ans;			if(belong[left]&1)				ans = query(left,left,1,tree_odd) - query(left,left,1,tree_even);			else				ans = query(left,left,1,tree_even) - query(left,left,1,tree_odd);			ans += nnum[x];			cout<<ans<<endl;		}	}}void output() {}int main() {	while(true) {		init();		if(input())return 0;		cal();		output();	}	return 0;}