Cloesest Common Ancestors
题目大意：给出一个n个节点的树，m组询问求两点LCA。
注释：n<=900.
想法：这题一看，我去，这不傻题吗？一看读入方式，完了，懵逼了... ...这题是考读入啊一大堆乱七八糟的东西，真正有用的只有里面的数... ...然后，我学了两个比较有用的东西。
1.scanf("%*d");其中，*表示读完就删，所以可以用来处理本题。
2.强大的nc+read()，在此不做介绍。
总之，初学LCA，这是另一道朴素的LCA，用桶记录即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000
using namespace std;
int to[N],nxt[N],tot,fa[N],deep[N],barrel[N];
int head[N];
bool v[N];
// inline char nc()
// {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
// }
// inline void read(int &x)
// {
// x=0;char c=nc();
// while(!isdigit(c))c=nc();
// while(isdigit(c))x=x*10+c-'0',c=nc();
// }
inline void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int pre,int step)
{
fa[x]=pre;
deep[x]=step;
for(int i=head[x];i;i=nxt[i])
{
dfs(to[i],x,step+);
}
}
inline int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
while(deep[x]>deep[y]) x=fa[x];
while(x!=y) x=fa[x],y=fa[y];
return x;
}
int main()
{
int n,m;
int a,b;
char s[];
while(~scanf("%d",&n))
{
tot=;
memset(head,,sizeof(head));
memset(v,false,sizeof(v));
memset(barrel,,sizeof(barrel)); // scanf("%d",&n);
for(int i=;i<=n;i++)
{
// read(a);
scanf("%*[^0-9]%d",&a);
// read(m);
scanf("%*[^0-9]%d",&m);
for(int i=;i<=m;i++)
{
scanf("%*[^0-9]%d",&b);
add(a,b);
v[b]=;
}
}
int root;
for(int i=;i<=n;i++)
{
if(!v[i])
{
root=i;
break;
}
}
dfs(root,root,);
scanf("%*[^0-9]%d",&m);
for(int i=;i<=m;i++)
{
scanf("%*[^0-9]%d",&a);
scanf("%*[^0-9]%d",&b);
barrel[lca(a,b)]++;
}
for(int i=;i<=n;i++)
{
if(barrel[i]!=) printf("%d:%d\n",i,barrel[i]);
}
scanf("%*[^0-9]");
}
}
小结：LCA的朴素算法还是很有用的啊... ...
错误：1.在读取链式前向星时一定要记得是i=nxt[i]而不是nxt[i]。
2.最后仍然会剩余一个括号，别忘记了它会影响下一组数据。