poj 1470 Closest Common Ancestors (LCA)

 1 //444K    485MS    C++    2082B    2014-04-15 19:41:38
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #define N 1005
 6 struct node{
 7     int u,v;
 8     int next;
 9 }edge[2*N];
10 int n,num,to,head[N];
11 int set[2*N],dep[2*N];
12 int rank[N],vis[N];
13 int dp[2*N][30];
14 void addedge(int u,int v)
15 {
16     edge[num].u=u;
17     edge[num].v=v;
18     edge[num].next=head[u];
19     head[u]=num++;
20 }
21 int Min(int a,int b)
22 {
23     return dep[a]<dep[b]?a:b;
24 }
25 void dfs(int u,int deep)
26 {
27     vis[u]=1;
28     set[++num]=u;
29     rank[u]=num;
30     dep[num]=deep;
31     for(int i=head[u];i!=-1;i=edge[i].next){
32         int v=edge[i].v;
33         if(vis[v]) continue;
34         dfs(v,deep+1);
35         set[++num]=u;
36         dep[num]=deep;
37     }
38 }
39 void init()
40 {
41     int nn=2*n-1;
42     int m=(int)(log(nn*1.0)/log(2.0));
43     for(int i=1;i<=nn;i++)
44         dp[i][0]=i;
45     for(int j=1;j<=m;j++)
46         for(int i=1;i+(1<<j)-1<=nn;i++)
47             dp[i][j]=Min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
48 }
49 int RMQ(int l,int r)
50 {
51     int m=(int)(log((r-l+1)*1.0)/log(2.0));
52     return Min(dp[l][m],dp[r-(1<<m)+1][m]);
53 }
54 int LCA(int a,int b)
55 {
56     int x=rank[a];
57     int y=rank[b];
58     if(x>y) return set[RMQ(y,x)];
59     else return set[RMQ(x,y)];
60 }
61 int main(void)
62 {
63     int m,u,v,mm;
64     int in[N];
65     while(scanf("%d",&n)!=EOF)
66     {
67         memset(in,0,sizeof(in));
68         memset(vis,0,sizeof(vis));
69         memset(head,-1,sizeof(head));
70         num=0;
71         for(int i=0;i<n;i++){
72             scanf("%d:(%d)",&u,&mm);
73             while(mm--){
74                 scanf("%d",&v);
75                 in[v]++;
76                 addedge(u,v);
77                 addedge(v,u);
78             }
79         }
80         int id=0;
81         num=0;
82         while(in[++id]);
83         dfs(id,1);
84         init();
85         memset(in,0,sizeof(in));
86         scanf("%d",&m);
87         //printf("%%%d\n",m);
88         while(m--){
89             scanf("%(%d %d%)",&u,&v); //这里蛋疼了一会 
90             //printf("*%d %d\n",u,v);
91             in[LCA(u,v)]++;
92         }
93         for(int i=1;i<=n;i++)
94             if(in[i]) printf("%d:%d\n",i,in[i]);
95     }
96     return 0;
97 }

 1 //3024K    563MS    C++    1575B    2014-04-15 20:32:44
 2 //Runtime Error 了好几次 T T 
 3 #include<iostream>
 4 #include<queue>
 5 #include<vector>
 6 #define N 1005
 7 using namespace std;
 8 vector<int>child[N],V[N];
 9 int set[N],vis[N];
10 int in[N];
11 int n;
12 void init()
13 {
14     for(int i=0;i<=n;i++){
15         child[i].clear();
16         V[i].clear();
17     }
18     memset(vis,0,sizeof(vis));
19     memset(in,0,sizeof(in));
20 }
21 int find(int x)
22 {
23     if(set[x]!=x) set[x]=find(set[x]);
24     return set[x];
25 }
26 void merge(int a,int b)
27 {
28     int x=find(a);
29     int y=find(b);
30     set[y]=x;
31 }
32 void LCA(int u)
33 {
34     set[u]=u;
35     vis[u]=true;
36     for(int i=0;i<V[u].size();i++)
37         if(vis[V[u][i]])
38             in[find(V[u][i])]++;
39     for(int i=0;i<child[u].size();i++){
40         if(!vis[child[u][i]]){
41             LCA(child[u][i]);
42             merge(u,child[u][i]);
43             set[child[u][i]]=u;
44         }
45     }
46 }
47 int main(void)
48 {
49     int m,u,v,mm;
50     
51     while(scanf("%d",&n)!=EOF)
52     {
53         init();
54         for(int i=0;i<n;i++){
55             scanf("%d:(%d)",&u,&mm);
56             while(mm--){
57                 scanf("%d",&v);
58                 child[u].push_back(v);
59                 child[v].push_back(u);
60                 in[v]++;
61             }
62         }
63         scanf("%d",&m);
64         for(int i=1;i<=m;i++){
65             scanf("%(%d %d%)",&u,&v);
66             V[u].push_back(v);
67             V[v].push_back(u);
68         }
69         int id=0;
70         while(in[++id]);
71         memset(in,0,sizeof(in));
72         LCA(id);
73         for(int i=1;i<=n;i++)
74             if(in[i]) printf("%d:%d\n",i,in[i]);
75     }    
76     return 0;
77 }