2450238_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INIT (tree *)malloc(sizeof(tree))
int changed;
int num[100001];
int visited[100001];

typedef struct node
{
	int adj;
	struct node *next;
}tree;

typedef struct Node
{
	int pa;
	bool app;
	tree *head;
}Adj;
Adj adj[100001];

int n;

int dfs(int v)
{
	tree *s;

	visited[v] = 1;
	s = adj[v].head;
	num[v] = adj[v].app;
	while(s->next)
	{
		if(!visited[s->next->adj]&&s->next->adj!=adj[v].pa)
			num[v] += dfs(s->next->adj);
		s = s->next;
	}
	return num[v];
}

void DFS(int pre,int v)
{
	tree *s;

	visited[v] = 1;
	s = adj[v].head;
	adj[v].pa = pre;
	while(s->next)
	{
		if(!visited[s->next->adj])
			DFS(v,s->next->adj);
		s = s->next;
	}
}

int main()
{
	int i, q;
	char ch[2];
	tree *s;
	int a, b;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		num[i] = 1;
		adj[i].head = INIT;
		adj[i].app = true;
		adj[i].head->next = NULL;
	}
	for(i = 0; i < n-1; i++)
	{
		scanf("%d%d",&a,&b);
		a--,b--;
		s = INIT;
		s->adj = b;
		s->next = adj[a].head->next;
		adj[a].head->next = s;
		s = INIT;
		s->adj = a;
		s->next = adj[b].head->next;
		adj[b].head->next = s;
	}
	scanf("%d",&q);
	changed = 0;
	dfs(0);
	memset(visited,0,sizeof(visited));
	DFS(-1,0);
	for(i = 0; i < q; i++)
	{
		scanf("%s%d",ch,&a);
		a--;
		if(ch[0]=='C')
		{
			adj[a].app = !adj[a].app;
			//changed = 1;
		}
		else
		{
			//if(changed)
			{
				//changed = 0;
				memset(visited,0,sizeof(visited));
				dfs(a);
				printf("%d\n",num[a]);
			}
			//else
			//	printf("%d\n",num[a]);
		}
	}
	return 1;
}