1141 参考答案

   1 /*
   2 zju 1141 CCA 最近共同祖先 并查集
   3 ymc 2008/6/11
   4 题目大意：
   5 给定一颗树，每次查询某两个节点的共同祖先。
   6 对所有的查询，输出被查询过的祖先节点已经查询的次数。
   7 解题思路：
   8 p[N]记录每个节点的父节点，L[N]记录节点所在的层次。
   9 如果要查询的两个节点u，v所在的层次不同，让层次深的节点
  10 追溯到与另外一个节点相同层次的祖先。然后每次让两个节点追溯
  11 到父节点，直到找到相同的祖先。
  12 */
  13 #include <iostream>
  14 using namespace std;
  15 const int N=1000;
  16 int p[N],L[N],An[N];
  17 int n;
  18 int CCA(int u,int v)
  19 {
  20         while(L[u]>L[v])
  21                 u=p[u];
  22         while(L[v]>L[u])
  23                 v=p[v];
  24         while(L[u])
  25         {
  26                 if(u==v)
  27                         break;
  28                 u=p[u];
  29                 v=p[v];
  30         }
  31         return u;
  32 }
  33 int main()
  34 {
  35         while(scanf("%d",&n)!=EOF)
  36         {
  37             memset(p,0,sizeof(p));
  38         memset(L,0,sizeof(L));
  39         memset(An,0,sizeof(An));
  40         int u,v,m;
  41         char tmp[2];
  42         for(int j=0;j<n;j++)
  43         {
  44             scanf("%d %1s %1s %d %1s",&u,tmp,tmp,&m,tmp);
  45             for(int i=0;i<m;i++)
  46             {
  47                 cin>>v;
  48                 p[v]=u;
  49                 L[v]=L[u]+1;
  50             }
  51         }
  52         scanf("%d",&m);
  53         for(int i=0;i<m;i++)
  54         {
  55             scanf("%1s %d %1s %d %1s",tmp,&u,tmp,&v,tmp);
  56             An[CCA(u,v)]++;
  57         }
  58         for(int i=1;i<=n;i++)
  59             if(An[i]>0)
  60                 printf("%d:%d\n",i,An[i]);
  61         }
  62 }