> #include <iostream>
> #define MAX 4096
> using namespace std;
> int graph[1000][1000],num[1000],level[1000],uset[1000];
> int E[5000],L[5000],R[5000],pp[10000];
> int sum;
> bool visit[1100];
> inline bool RMQcmp(int i, int j)
> { 
>     return L[i] > L[j];
> }    
> int root(int v)
> {
>     if(uset[v] == v)
>       return v;
>     uset[v] = root(uset[v]);
>     return uset[v];
> } 
> int Union(int a,int b)
> {
> 	uset[uset[b]]=uset[a];
> 	return 0;
> }
> void RMQCreate()        
> { 
>      int f = MAX, t = MAX + sum - 1, i; 
>      for(i = 0; i < sum; ++i) 
>         pp[i+MAX] = i; 
>      for( ;f < t; f /= 2, t /= 2) 
>      { 
>         for(i = f; i < t ; i+= 2) 
>         { 
>             if( !RMQcmp(pp[i], pp[i+1]) ) 
>                 pp[i/2] = pp[i]; 
>             else pp[i/2] = pp[i+1]; 
>         } 
>         if(!(t&1)) pp[t/2] = pp[t]; 
>      } 
> } 
> int RMQFind(int ss, int ee) 
> { 
>     int k, f, t; 
>     ss += MAX, ee += MAX; 
>     k = !RMQcmp(pp[ss] ,pp[ee]) ? pp[ss] : pp[ee]; 
>     for( f = ss, t = ee; f < t; f/=2, t/=2) 
>     { 
>         if( !(f&1) && f + 1 < t && !RMQcmp(pp[f+1], k)) 
>             k = pp[f+1]; 
>         if( (t&1)  && t - 1 > f && !RMQcmp(pp[t-1], k)) 
>             k = pp[t-1]; 
>     } 
>     return k; 
> } 
> int dfs (int v,int l)
> {
>    E[sum++]=v;
>    level[v]=l;
>    for (int i=0;i<num[v];i++)
> 		if (!visit[graph[v][i]])
> 		{
> 			visit[graph[v][i]]=true;
> 			dfs(graph[v][i],l+1);
> 			E[sum++]=v;
> 		}
>    return 0;
> }
> main ()
> {
> 	int n,u,v,m,i,j;
> 	char a;
> 	while (scanf ("%d",&n)!=EOF)
> 	{
> 		for (i=1;i<=n;i++)  
> 		{
> 			uset[i]=i;
> 		    num[i]=0,visit[i]=false,R[i]=-1,level[i]=100000;
> 		}
> 		for (i=0;i<n;i++)
> 		{
> 			scanf("%d",&v);
> 			while(scanf("%c",&a)&&a!='(');
> 			scanf("%d",&m);
> 			while(scanf("%c",&a)&&a!=')');
> 			num[v]=m;
> 			for (j=0;j<m;j++)
> 			{
> 		        scanf ("%d",&graph[v][j]);
> 		        if (root(v)!=root(graph[v][j]))
> 		            Union(v,graph[v][j]);
> 			}
> 		}
> 		sum=0;
> 		visit[uset[v]]=true;
> 		dfs(uset[v],0);
> 		for (i=0;i<sum;i++)
> 		{
> 			L[i]=level[E[i]];
> 			if (R[E[i]]==-1)
> 			   R[E[i]]=i;
> 		}
> 		RMQCreate();
> 		for (i=1;i<=n;i++)
> 		    num[i]=0;
> 		scanf ("%d",&m);
> 		while (m--)
> 		{
> 			while(scanf("%c",&a)&&a!='(');
> 			scanf("%d%d",&u,&v);
> 			if (R[u]<=R[v])
> 			    num[E[RMQFind(R[u],R[v])]]++;
> 			else
> 			    num[E[RMQFind(R[v],R[u])]]++;
> 			while(scanf("%c",&a)&&a!=')');
> 		}
> 		for (i=1;i<=n;i++)
> 			if (num[i])
> 			   printf ("%d:%d\n",i,num[i]);
> 	}
> }                                                                                                       

• 多case！！！！ (0) xiaolonghingis 2006-09-07 17:24:14
  • 多case！！！！ (9) wer2 2007-10-13 21:01:57
    • Re:多case！！！！ (21) liujatp 2008-11-27 00:03:32
• Re:刚在zoj上交也AC了 (99) wpc0000 2007-03-03 13:43:51