#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]);
	}
}                                                                                                       

• 刚在zoj上交也AC了 (2798) xiaolonghingis 2006-09-06 20:28:49
  • 多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
• Re:谁能帮看看，实在是找不到错误，WA的郁闷阿。。。谢谢 (94) cassiopeia 2008-08-15 18:13:34