前言
因?yàn)槲以谧鲱}目的過(guò)程中捏卓，WA了（最后發(fā)現(xiàn)是數(shù)組開(kāi)小了的緣故），我以為我方法錯(cuò)誤慈格。然后百度一下怠晴，滿(mǎn)屏的LCA在線(xiàn)/離線(xiàn)算法。加上長(zhǎng)篇代碼浴捆。為了拯救茫茫的ACMer蒜田，我決定吐槽一下在這題中使用LCA算法的人
題意
給出一顆樹(shù)，給出若干個(gè)查詢(xún)选泻，每個(gè)查詢(xún)是樹(shù)的兩個(gè)節(jié)點(diǎn)冲粤，要求的是這兩個(gè)節(jié)點(diǎn)的最近公共祖先。最后總計(jì)每個(gè)數(shù)作為最近公共祖先出現(xiàn)的次數(shù)页眯。說(shuō)白了就是最近公共祖先問(wèn)題梯捕。
解析
的確，LCA是用于求最近公共祖先的一種有效算法窝撵，但是由于思想比較復(fù)雜（從根節(jié)點(diǎn)開(kāi)始搜索）且代碼量太大了（隨便找了一篇就是180行的長(zhǎng)度）傀顾，所以在這里并不推薦用。如果只是要A這道題碌奉，那大可以這樣
比如要查(3,4)最近公共祖先
從3開(kāi)始往上走短曾，得到：[3,2,5]
從4開(kāi)始往上走，得到：[4,5]
然后倒序遍歷赐劣，5和5相同嫉拐，繼續(xù)比較2和4，2和4不同魁兼，則上一個(gè)公共祖先 5 就是最近的公共祖先
再比如要查(2,3)最近公共祖先
從2開(kāi)始往上走椭岩，得到：[2,5]
從3開(kāi)始往上走，得到[3,2,5]
然后倒序遍歷，5和5相同判哥，繼續(xù)比較2和2也相同献雅，繼續(xù)比較3和X(X表示越界，比較失敗)塌计，則上一個(gè)公共祖先2就是最近的公共祖先
LCA算法在于從根節(jié)點(diǎn)開(kāi)始遍歷挺身，在深度優(yōu)先搜索的過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行“染色”操作。我覺(jué)得至少在這里锌仅，貌似簡(jiǎn)單的“白話(huà)文”（如上題解過(guò)程）更能讓人理解章钾，簡(jiǎn)單的題目，就用簡(jiǎn)單的理解+簡(jiǎn)單的代碼热芹，簡(jiǎn)單也是一種習(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;
}
