前言
因?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;
}