pku 3321ツリー配列

近頃光が木の配列に遭遇しているのを発見しましょう...http://poj.org/problem?id=3321 ツリーが与えられ、ルートノードは常に1であり、各ノードの値は最初は1であり、次に、ノードの下にあるノードの総数をクエリーする2つの操作と、ノードの値を逆方向(1から0、0から1)にします.この問題は先日のhdu 3887と似ています...いずれも逆序数を求める方法を利用している.しかし、この問題では、ノードにシーケンスを再作成する方法(タイムスタンプと呼ばれる人もいる)が用いられています.いずれにしても、ノードを後の順序で再編成することで、このノードに初めて入ったときの番号bと、このノードを離れたときの番号cを記録することで、あるノードのサブツリー上のノード番号がその番号より小さいことを保証することができます.そして私たちが維持している値は[b,c]という区間の和です.の注意この問題は意外にもstlを押さえました...最后に自分で隣接表390 msを书いたことがあります...私はまた自分でスタックをシミュレートして再帰して、直接dfsもスタックを爆発させないようです..コード:

#include<vector>
#include<iostream>
using namespace std;

const int N=200010;
int n, q, sum[N], vis[N], b[N], c[N], cn, stk[N], a[N];
int first[N], en;
struct node
{
	int v, next;
} edge[N];

int query(int i)
{
	int tmp=0;
	for(; i>0; i-=i&(-i))
		tmp += sum[i];
	return tmp;
}
void update(int i, int v)
{
	for(; i<=n; i+=i&(-i))
		sum[i] += v;
}

void dfs()
{
	int i, j, sn;
	for(i=0; i<=n; i++)
		vis[i] = 0;

	sn = 0;
	cn = 1;
	stk[sn++] = 1;
	vis[1] = 1;
	while(sn!=0)
	{
		i = stk[sn-1];
		if(vis[i]==1)
		{
			b[i] = cn;
			vis[i] = 2;
		}
		if(first[i]!=-1)
		{
			j = first[i];
			if(vis[edge[j].v]==0)
			{
				stk[sn++] = edge[j].v;
				vis[edge[j].v] = 1;
			}
			first[i] = edge[j].next;
		}
		else
		{
			c[i] = cn++;
			sn--;
		}
	}
}

void add(int x, int y)
{
	edge[en].v = y;
	edge[en].next = first[x];
	first[x] = en++;
}

int main()
{
	int i, x, y, v;
	char op[3];
	while(scanf("%d", &n)!=EOF)
	{
		if(n==0)
			return 0;
		for(i=0; i<=2*n; i++)
			first[i] = -1;
		en = 0;
		for(i=1; i<n; i++)
		{
			scanf("%d%d", &x, &y);
			add(x, y);
			add(y, x);
		}
		dfs();
		for(i=0; i<=n; i++)
			sum[i] = 0;
		for(i=1; i<=n; i++)
		{
			update(i, 1);
			a[i] = 1;
		}
		scanf("%d", &q);
		while(q--)
		{
			scanf("%s %d", op, &v);
			if(op[0]=='Q')
				printf("%d
", query(c[v])-query(b[v]-1));
			else
			{
				if(a[c[v]]==1)
				{
					update(c[v], -1);
					a[c[v]] = 0;
				}
				else
				{
					update(c[v], 1);
					a[c[v]] = 1;
				}
			}
		}
	}
	return 0;
}