前言
因为我在做题目的过程中，WA了（最后发现是数组开小了的缘故），我以为我方法错误。然后百度一下，满屏的LCA在线/离线算法。加上长篇代码。为了拯救茫茫的ACMer，我决定吐槽一下在这题中使用LCA算法的人
附上 LCA算法的简介
题意
给出一颗树，给出若干个查询，每个查询是树的两个节点，要求的是这两个节点的最近公共祖先。最后总计每个数作为最近公共祖先出现的次数。说白了就是最近公共祖先问题。
解析
的确，LCA是用于求最近公共祖先的一种有效算法，但是由于思想比较复杂（从根节点开始搜索）且代码量太大了（随便找了一篇就是180行的长度），所以在这里并不推荐用。如果只是要A这道题，那大可以这样
比如要查(3,4)最近公共祖先
从3开始往上走，得到：[3,2,5]
从4开始往上走，得到：[4,5]
然后倒序遍历，5和5相同，继续比较2和4，2和4不同，则上一个公共祖先 5 就是最近的公共祖先
再比如要查(2,3)最近公共祖先
从2开始往上走，得到：[2,5]
从3开始往上走，得到[3,2,5]
然后倒序遍历，5和5相同，继续比较2和2也相同，继续比较3和X(X表示越界，比较失败)，则上一个公共祖先2就是最近的公共祖先
LCA算法在于从根节点开始遍历，在深度优先搜索的过程中对结点进行“染色”操作。我觉得至少在这里，貌似简单的“白话文”（如上题解过程）更能让人理解，简单的题目，就用简单的理解+简单的代码，简单也是一种习惯
AC代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#define maxn 101000
using namespace std;
int dp1[maxn],dp2[maxn],dp[maxn],tree[maxn];
int main(int argc, const char * argv[]) {
int n,m,p,d,len1,len2;
char ch;
while(cin>>n){
memset(dp, 0, sizeof(dp));
memset(tree, 0, sizeof(tree));
while(n--){
scanf("%d:(%d)",&p,&d);
for(int i=0; i<d; i++){
scanf("%d",&m);
tree[m] = p;
}
}
cin>>m;
for(int j=0; j<m; j++){
len1 = 0; len2 = 0;
cin>>ws>>ch>>p>>ch>>d>>ch;
while(p){
dp1[len1++] = p;
p = tree[p];
}
while(d){
dp2[len2++] = d;
d = tree[d];
}
while(dp1[--len1]==dp2[--len2]);
dp[dp1[len1+1]]++;
}
for(int i=1; i<=1010; i++)
if(dp[i]) cout<<i<<":"<<dp[i]<<endl;
}
return 0;
}
