描述

给定一棵n个节点的树，节点编号为1, 2, …, n。树中有n - 1条边，任意两个节点间恰好有一条路径。这是一棵彩色的树，每个节点恰好可以染一种颜色。初始时，所有节点的颜色都为0。现在需要实现两种操作:

1. 改变节点x的颜色为y；

2. 询问整棵树被划分成了多少棵颜色相同的子树。即每棵子树内的节点颜色都相同，而相邻子树的颜色不同。

输入

第一行一个整数T，表示数据组数，以下是T组数据。

每组数据第一行是n，表示树的节点个数。接下来n - 1行每行两个数i和j，表示节点i和j间有一条边。接下来是一个数q，表示操作数。之后q行，每行表示以下两种操作之一：

1. 若为"1"，则询问划分的子树个数。

2. 若为"2 x y"，则将节点x的颜色改为y。

输出

每组数据的第一行为"Case #X:"，X为测试数据编号，从1开始。

接下来的每一行，对于每一个询问，输出一个整数，为划分成的子树个数。

数据范围

1 ≤ T ≤ 20

0 ≤ y ≤ 100000

小数据

1 ≤ n, q ≤ 5000

大数据

1 ≤ n, q ≤ 100000

样例输入

231 22 3312 2 1151 22 32 42 5412 2 12 3 21

样例输出

Case #1:13Case #2:15 分析： 可以用图的深度遍历或者树的深度遍历来解决。 图的遍历

#include
     
      #include
      
       using namespace std;#define MAXVEX  100000             //最大顶点数，应由用户定义typedef struct EdgeNode         //边表结点{	int adjvex;         //邻接点域，存储该顶点对应的下标		struct EdgeNode *next;      //链域，指向下一个邻接点}EdgeNode;typedef struct VertexNode       //顶点表结构{	int color;        //顶点域，存储顶点信息	EdgeNode *firstedge;        //边表头指针}VertexNode, AdjList[MAXVEX];typedef struct{	AdjList adjList;	int numVertexes, numEdges;  //图中当前顶点数和边数}GraphList;//建立图的邻接表结构void CreateGraph(GraphList *g){	int i, j, k;	EdgeNode *e;	EdgeNode *f;	cin>>g->numVertexes;	g->numEdges = g->numVertexes-1;	for(i = 1; i <= g->numVertexes; i++)	{		g->adjList[i].color = 0;          //输入顶点信息		g->adjList[i].firstedge = NULL;          //将边表置为空表			}	//建立边表	for(k = 0; k < g->numEdges; k++)	{				int p,q;		cin>>p>>q;		//向内存申请空间，生成边表结点		e = (EdgeNode *)malloc(sizeof(EdgeNode));				//邻接序号为j		e->adjvex = q;		//将e指针指向当前顶点指向的结构		e->next = g->adjList[p].firstedge;		//将当前顶点的指针指向e		g->adjList[p].firstedge = e;		f = (EdgeNode *)malloc(sizeof(EdgeNode));				f->adjvex = p;		f->next = g->adjList[q].firstedge;		g->adjList[q].firstedge = f;	}}bool visited[MAXVEX];//邻接表的深度递归算法void DFS(GraphList& g, int i){	EdgeNode *p;	visited[i] = true;	p = g.adjList[i].firstedge;	while(p)	{		if(!visited[p->adjvex] && (g.adjList[i].color == g.adjList[p->adjvex].color))		{			DFS(g, p->adjvex);           //对访问的邻接顶点递归调用		}		p = p->next;	}}//邻接表的深度遍历操作int DFSTraverse(GraphList& g){	int cnt=0;	int i;	for(i = 1; i <= g.numVertexes; i++)	{		visited[i] = false;	}	for(i = 1; i <= g.numVertexes; i++)	{		if(!visited[i])		{			DFS(g, i);			cnt++;		}	}	return cnt;}int main(){	int T;	int n;	int q;	int x,y;	int chs;	vector
       
        
          > vvec;	vector
         
           vec;	GraphList g;	cin>>T;	while(T--)	{		vec.clear();		CreateGraph(&g);		cin>>q;		for(int i=0; i
          
           >chs; if(chs==1) { vec.push_back(DFSTraverse(g)); } if(chs==2) { cin>>x>>y; g.adjList[x].color = y; } } vvec.push_back(vec); } for(int i=0; i
          
         
        
       
      
     

　　

树的遍历

#include
     
      #include 
      
       const int maxVex = 100000;using namespace std;int parent[maxVex];int child[maxVex];int color[maxVex];bool visited[maxVex];int num; //tree node numbervoid create(){	int x,y;	cin>>num;	for (int i=1; i<=num; i++)	{		parent[i]=0;		child[i]=0;		color[i]=0;	}	for(int i=0; i
       
        >x>>y;		child[x]=y;		parent[y]=x;	}}void DFS(int i){	visited[i] = true;	for (int j = child[i]; j<=num&&j>=1&&color[i]==color[j]; j = child[j])	{		if(!visited[j])			DFS(j);	}	for (int j = parent[i]; j<=num&&j>=1&&color[i]==color[j]; j = parent[j])	{		if(!visited[j])			DFS(j);	}}int DFSTraverse(){	int cnt=0;	for(int i=1; i<=num; i++)	{		visited[i]=false;	}	for(int i=1; i<=num; i++)	{		if(!visited[i])		{                                                                                                                                                                                                           			DFS(i);			cnt++;		}	}	return cnt;}int main(){	int T;	int n;	int q;	int x,y;	int chs;	vector
        
         
           > vvec;	vector
          
            vec; cin>>T; while(T--) { vec.clear(); create(); cin>>q; for(int i=0; i
           
            >chs; if (chs==1) { vec.push_back(DFSTraverse()); } if(chs==2) { cin>>x>>y; color[x]=y; } } vvec.push_back(vec); } for(int i=0; i
           
          
         
        
       
      
     

　　

http://blog.csdn.net/linxinyuluo/article/details/6847851