Codeforces ラウンド #225 (ディビジョン 1) C ツリー配列 Tree_html/css_WEB-ITnose

この質問を見てとてもうれしく思います。私が以前に行ったことと非常に似ているという印象があります。タイムスタンプを間隔として使用してツリー配列を構築します。質問は、x ポイント val を追加し、その下のすべてのノードに -val を追加するという意味だと思いました。したがって、最初に 2 つのツリー配列が加算と減算によって確立され、最後の減算が答えになることがわかりました。質問を読んでも見つからなかったので、その文を誤解していました。そして、これを読みました:
http://blog.csdn.net/keshuai19940722/article/details/ 18967661
処理部分をよく見るとパリティ解析があるのか​​と思っていました ルールについては質問の読み方を間違えていたことに後から気づきました x点にvalを付け、子ノードに-valを付けていることが分かりました。直接接続されている場合、val はその子ノードの子ノードに追加されます。 。 。ははは。 。クライ

方法は、このツリーに対して dfs を実行し、奇数と偶数で表される現在の層番号との関係を記録し、各ノードのタイムスタンプを使用します。間隔ツリーを構築するために dfs が行われ、最後に奇数と偶数が分離され、加算は 1 つのツリー配列で行われ、減算は別のツリー配列で行われます。その後、単一の点の値が最終的に計算されます。この点が属するルート ノードからの距離、つまり、追加された値は、別のツリー配列で減算される必要がある対応する値から減算され、各ノード自体の値はツリーに追加されません。先頭に配列を追加し、元の値を追加する必要があります。これが答えです

次に、タイムスタンプを使用して、ルートからのノードのパリティを記録し、2 つを確立しました。線分ツリー、奇数処理を記録したものと偶数処理を記録した結果、どこが間違っているのかわからず、うまくいかない場合は長い間修正しました。 、また習ったことをすっかり忘れてしまいました。 。 。

ツリー配列の場合:

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

線分ツリーの場合:

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