//注意，输入顺序不一定从根节点开始
#include<stdio.h>
#include<string.h>
// P55 第四种算法RMQ
int tree[1001][1001];
char string[1001];
int pointfather[1001];
int num_of_child[1001];
int E[1001];
int R[1001];
int children[1001];
int childrennum[1001];
int shendu[1001];
void DFS(int);
int LCA(int ,int);
int e=1,r=1;
int main()
{
	int num_of_vertices;
	int num_of_pairs;
	int i,k;
	int father;
	int z;
	int w;
//	char ch;
	int root,t;
	int a,b;
//	int flag;
	int ancestor;
	int total=0;
	int num;
	int onlychild;
	scanf("%d ",&num_of_vertices);
	for(z=0;z<num_of_vertices;z++)
	{
		gets(string);
		i=0;
		father=int(string[i])-48;
		i++;
		k=0;
		while(i<int(strlen(string)))
		{
			if(string[i-1]=='('&&string[i+1]==')')
			{
				num=int(string[i])-48;
				num_of_child[father]=num;
			}
			else if(string[i]<='9'&&string[i]>='1')
			{
				onlychild=int(string[i])-48;
				tree[father][k++]=onlychild;
				pointfather[onlychild]=father;
			}
			i++;
		}
	}
	for(w=1;w<=num_of_vertices;w++)
		if(pointfather[w]!=0)
			children[pointfather[w]]++;
	for(w=1;w<=num_of_vertices;w++)
		if(pointfather[w]!=0)
			root=w;
		while(pointfather[root]!=0)
			root=pointfather[root];
		DFS(root);      //深搜
		scanf("%d ",&num_of_pairs);
		for(z=0;z<num_of_pairs;z++)
		{
			gets(string);
			for(i=0;i<int(strlen(string));i++)
			{
				if(string[i]=='(')
				{
					a=int(string[i+1])-48;
					b=int(string[i+3])-48;				
				total++;
				ancestor=LCA(a,b);
				childrennum[ancestor]=childrennum[ancestor]+1;
				if(total>=num_of_pairs)
					break;
				}
			}
			if(total>=num_of_pairs)
				break;
		}
		//调试语句j
/*	   for(int v=0;v<=5;v++)
		{
			printf("%d   ",v);
			for(int vv=0;vv<=5;vv++)
				printf("%d ",tree[v][vv]);
			printf("\n");
		}*/
		for(t=0;t<1001;t++)
		{
			if(childrennum[t]>0)
				printf("%d:%d\n",t,childrennum[t]);
		}
	return 0;
}
void DFS(int root)
{
	int z;
	if(pointfather[root]!=0)
		shendu[root]=shendu[pointfather[root]]+1;
	else
		shendu[root]=1;
	E[e]=root;
	if(R[root]==0)
		R[root]=e;
	e++;
	if(tree[root][0]==0)
	{
		E[e]=root;
		e++;
	}
	else
	{
		for(z=0;z<children[root];z++)
		{
			DFS(tree[root][z]);
			tree[root][z]=0;
			E[e]=root;
			e++;
		}
	}
}
int LCA(int a,int b)
{
	int min=100000000;
//	int middle;
	int flag;
	int x;
	int before,last;
	if(R[a]<R[b])
	{
		before=R[a];
		last=R[b];
	}
	else
	{
		before=R[b];
		last=R[a];
	}
	for(int i=before;i<=last;i++)
	{
		x=E[i];
		if(shendu[x]<min)
		{
			min=shendu[x];
			flag=x;
		}
	}
	return flag;
}



			
			

• Re:哪为大牛帮忙看看啊，老是超时。代码如下（RMQ算法） (46) ACM06019 2007-02-07 19:49:00