萌新站外水题求助

【问题描述】
有一颗树，求给定两节点的公共祖先，最后输出每个节点当做祖先的次数。

【输入格式】
输入文件包含多组测试数据。

对于每组测试数据的第一行为一个整数 n
�
（1≤n≤900
1
≤
�
≤
900
），表示结点个数；

接下来 n
�
 行，每行输入形式为 k:(t)k1,k2,…,kt
�
:
(
�
)
�
1
,
�
2
,
…
,
�
�
，其中：

第一个数字 k
�
，表示结点 k
�
；t
�
 表示 k
�
 的儿子个数，k1,k2,…,kt
�
1
,
�
2
,
…
,
�
�
 分别表示 k
�
 的儿子节点编号。

第 n+2
�
+
2
 行为一个整数表示询问最近公共祖先的结点对数

接下来若干行来描述询问的结点，用一对括号括起来。

【输出格式】
对于每组数据输出若干行，每行形式为 a:b
�
:
�
，表示结点 a
�
 做公共祖先有 b
�
 次，按照结点 a
�
 的顺序输出。

【样例输入1】
5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1,5)
(1,4)
(4,2)
(2,3)
(1,3)
(4,3)
【样例输出1】
2:1
5:5
【样例1解释】


【数据范围及约定】
对于所有数据，1≤n≤900
1
≤
�
≤
900
。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 1e3 + 1, M = 2 * N;

int n, m;
int cnt[N];
int rt;
int p[N][20];
int h[N], e[M], ne[M], idx, d[N], fa[N];

inline void add(int a, int b)
{
    e[++idx] = b, ne[idx] = h[a], h[a] = idx ;
} 

inline void dfs(int x, int de)
{
    d[x] = de;
    for (int i = h[x]; i; i = ne[i])
    {
        int j = e[i];
        if (e[i] == fa[x]) continue;
        fa[j] = x;
        dfs(j, de + 1);
    }
}

inline void init()
{
    memset(p, -1, sizeof p);
    for (int i = 1; i <= n; i ++ ) p[i][0] = fa[i];
    for (int j = 1; (1 << j) <= n; j ++ )
      for (int i = 1; i <= n; i ++ )
        if (p[i][j - 1] != -1)
          p[i][j] = p[p[i][j - 1]][j - 1];
}

inline int lca(int a, int b)
{
    if (d[a] < d[b]) swap(a, b);
    int k;
    for (k = 0; (1 << (k + 1)) <= d[a]; k ++);
    for (int i = k; i >= 0; i --)
      if (d[a] - (1 << i) >= d[b])
        a = p[a][i];
    if (a == b) return a;
    for (int i = k; i >= 0; i --)
      if (p[a][i] != -1 && p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
    return p[a][0];
}

inline void solve()
{
    memset(fa, -1, sizeof fa);
    memset(h, -1, sizeof h);
    memset(cnt, 0, sizeof cnt);
    int npy = n;
    int k, t, y;
    while (npy -- )
    {
        scanf("%d%d", &k, &t);
        while (t -- )
        {
            scanf("%d", &y);
            add(k, y);
            add(y, k);
            fa[y] = k;
        }
    }
    for (int i = 1; i <= n; i ++ )
      if (fa[i] == -1)
      {
        rt = i;
        break;
      }
    dfs(rt, 1);
    init();
    int did;
    scanf("%d", &did);
    int xx, yy;
    while (did -- )
    {
        scanf("%d%d", &xx, &yy);
        cnt[lca(xx, yy)] ++ ;
    }
    for (int i = 1; i <= n; i ++ )
      if (cnt[i] != 0)
       printf("%d:%d\n", i, cnt[i]);        
}

int main()
{
    while (cin >> n)solve();
    return 0;
}