前言

因為我在做題目的過程中，WA了（最后發(fā)現(xiàn)是數(shù)組開小了的緣故），我以為我方法錯誤。然后百度一下，滿屏的LCA在線/離線算法。加上長篇代碼。為了拯救茫茫的ACMer，我決定吐槽一下在這題中使用LCA算法的人

附上 LCA算法的簡介

題意

給出一顆樹，給出若干個查詢，每個查詢是樹的兩個節(jié)點，要求的是這兩個節(jié)點的最近公共祖先。最后總計每個數(shù)作為最近公共祖先出現(xiàn)的次數(shù)。說白了就是最近公共祖先問題。

解析

的確，LCA是用于求最近公共祖先的一種有效算法，但是由于思想比較復(fù)雜（從根節(jié)點開始搜索）且代碼量太大了（隨便找了一篇就是180行的長度），所以在這里并不推薦用。如果只是要A這道題，那大可以這樣

比如要查(3,4)最近公共祖先
從3開始往上走，得到：[3,2,5]
從4開始往上走，得到：[4,5]
然后倒序遍歷，5和5相同，繼續(xù)比較2和4，2和4不同，則上一個公共祖先 5 就是最近的公共祖先

再比如要查(2,3)最近公共祖先
從2開始往上走，得到：[2,5]
從3開始往上走，得到[3,2,5]
然后倒序遍歷，5和5相同，繼續(xù)比較2和2也相同，繼續(xù)比較3和X(X表示越界，比較失敗)，則上一個公共祖先2就是最近的公共祖先

LCA算法在于從根節(jié)點開始遍歷，在深度優(yōu)先搜索的過程中對結(jié)點進行“染色”操作。我覺得至少在這里，貌似簡單的“白話文”（如上題解過程）更能讓人理解，簡單的題目，就用簡單的理解+簡單的代碼，簡單也是一種習(xí)慣

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;
}