pku 3321 子树孩子数.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
#define PB push_back
//PKU 3321 子树孩子数

#define NMAX 1000005
#define MMAX 1000005
#define INFI 99999999

typedef struct ooparc
{
	int first;
	int second;
}ooparc;

typedef struct oopnode
{//在重复边集中，（arc.fisrt已排序），arc.first对应的开始点和结束点
	int begin;
	int end;
	int has;//自己本身的是否有苹果
	int count;//自己和子树的苹果树
	int fa;//父节点
}oopnode;

ooparc arc[MMAX*2];
oopnode node[NMAX];
//int index[NMAX];//点的索引，升序排列

bool cmparc(ooparc a,ooparc b)
{
	return a.first<b.first;
}

int build(int now)
{
	int sum=1,i,p;
	node[now].has=1;
	for(i=node[now].begin;i<=node[now].end;i++)
	{
		p=arc[i].second;
		if(node[now].fa!=p)
		{
			node[p].fa=now;
			sum+=build(p);
		}
	}
	node[now].count=sum;
	return sum;
}

void init(int mnum)
{
	int i;
	for(i=1;i<=mnum;i++) 
	{
		arc[mnum+i].first=arc[i].second;
		arc[mnum+i].second=arc[i].first;
	}
	sort(arc+1,arc+2*mnum+1,cmparc);
	node[arc[1].first].begin=1;
	for(i=2;i<=2*mnum;i++)
	{
		if(arc[i-1].first!=arc[i].first) 
		{
			node[arc[i].first].begin=i;
			node[arc[i-1].first].end=i-1;
		}
	}
	node[arc[i-1].first].end=2*mnum;
	for(i=1;i<NMAX;i++)
	{
		node[i].has=node[i].count=0;
		node[i].fa=-10;
	}
	node[1].fa=-1;
	build(1);
}

void add(int now)
{
	while(now!=-1)
	{
		node[now].count++;
		now=node[now].fa;
	}
}

void del(int now)
{
	while(now!=-1)
	{
		node[now].count--;
		now=node[now].fa;
	}
}

void change(int now)
{
	if(node[now].has==0)
	{
		node[now].has=1;
		add(now);
	}
	else
	{
		node[now].has=0;
		del(now);
	}
}

int cal(int now)
{
	return node[now].count;
}

int main()
{
	int num,i,qnum,x,y;
	char str[3];
	scanf("%d",&num);
	for(i=1;i<=num-1;i++)
	{
		scanf("%d %d",&arc[i].first,&arc[i].second);
	}
	init(num-1);
	scanf("%d",&qnum);
	for(i=1;i<=qnum;i++)
	{
		scanf("%s %d",&str,&x);
		if(str[0]=='Q') printf("%d\n",cal(x));
		else change(x);
	}
	return 0;
}