Description
Write a program that takes as input a rooted tree and a list of pairs of vertices. For each pair (u,v) the program determines the closest common ancestor of u and v in the tree. The closest common ancestor of two nodes u and v is the node w that is an ancestor of both u and v and has the greatest depth in the tree. A node can be its own ancestor (for example in Figure 1 the ancestors of node 2 are 2 and 5)
动态LCA，读入有些麻烦，练了练读入优化，并且对getchar()函数学习了一发，getchar()函数返回值为字符的ASC码，出错时返回-1。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 1000
#define M 1000000
int n,to[N],nxt[N],cnt,head[N],num[N];
char st[N];
bool v[N];
int headq[N],toq[M],nxtq[M],cntq,fa[N],root;
void addq(int x,int y)
{
toq[++cntq]=y;
nxtq[cntq]=headq[x];
headq[x]=cntq;
}
int read()
{
char ch=getchar();int re=0;
if(ch==-1)return 0;
while(ch!=-1&&(ch<'0'||ch>'9')) ch=getchar();
while(ch>='0'&&ch<='9'&&ch!=-1)re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int find(int x)
{
return fa[x]==x ? x:fa[x]=find(fa[x]);
}
void dfs(int x,int pre)
{
//printf("%d\n",x);
int i,y;
for(i=head[x];i;i=nxt[i])
dfs(to[i],x),fa[to[i]]=x;//回溯的时候更新fa
v[x]=1;//确保搜回当前结点有效，但由于特判了num++，所以写在后面也没有关系
for(i=headq[x];i;i=nxtq[i])
{
if(v[y=toq[i]])
{
num[find(y)]++;
//printf("%d %d %d\n",find(y),x,y);
}
}
//puts("re");
}
void clear()
{
int i;
for(i=1;i<=n;i++) fa[i]=i;
cnt=cntq=0;
memset(head,0,sizeof(head));
memset(headq,0,sizeof(headq));
memset(num,0,sizeof(num));
memset(v,0,sizeof(v));
}
int main()
{
n=read();
while(n)
{
clear();
int i,k1,k2,x;
for(i=1;i<=n;i++)
{
k1=read();x=read();
while(x--)
k2=read(),add(k1,k2),v[k2]=1;
}
for(i=1;i<=n;i++)
if(!v[i])
{
root=i;break;
}
memset(v,0,sizeof(v));
int t=read();
while(t--)
{
k1=read();k2=read();
if(k1==k2) num[k1]++;
else addq(k1,k2),addq(k2,k1);//双向离散化问题，保证先后顺序，所以只会加一次
}
dfs(root,root);//pre=root，保证根的fa就是根
for(i=1;i<=n;i++)
if(num[i])
printf("%d:%d\n",i,num[i]);
n=read();
}
return 0;
}