pku 3321 link.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 fa;
	ooplink *other;
}oopnode;

typedef struct ooplink
{
	int data;
	ooplink *next;
}ooplink;

ooplink *link;

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

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

int build(int now)
{
	int i,p;
	ooplink *temp,*tt;
	node[now].has=1;
	temp=(ooplink *)malloc(sizeof(ooplink));
	temp->next=NULL;
	ooplink->other=temp;
	tt=temp;
	for(i=node[now].begin;i<=node[now].end;i++)
	{
		p=arc[i].second;
		if(node[now].fa!=p)
		{
			temp=(ooplink *)malloc(sizeof(ooplink));
			temp->next=NULL;
			tt->data=p;
			tt->next=temp;
			tt=tt->next;
			node[p].fa=now;
		}
	}
	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=0;
		node[i].fa=-10;
	}
	node[1].fa=-1;
	build(1);
}

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