描述
上上回說到，小Hi和小Ho使用了Tarjan算法來優化了他們的“最近公共祖先”網站，但是很快這樣一個離線算法就出現了問題：如果隻有一個人提出了詢問，那麼小Hi和小Ho很難決定到底是針對這個詢問就直接進行計算還是等待一定數量的詢問一起計算。畢竟無論是一個詢問還是很多個詢問，使用離線算法都是隻需要做一次深度優先搜尋就可以了的。
那麼問題就來了，如果每次計算都隻針對一個詢問進行的話，那麼這樣的算法事實上還不如使用最開始的樸素算法呢！但是如果每次要等上很多人一起的話，因為說不準什麼時候才能夠湊夠人——是以事實上有可能要等上很久很久才能夠進行一次計算，實際上也是很慢的！
“那到底要怎麼辦呢？在等到10分鐘，或者湊夠一定數量的人兩個條件滿足一個時就進行運算？”小Ho想出了一個折衷的辦法。
“哪有這麼麻煩！别忘了和離線算法相對應的可是有一個叫做線上算法的東西呢！”小Hi笑道。
小Ho面臨的問題還是和之前一樣：假設現在小Ho現在知道了N對父子關系——父親和兒子的名字，并且這N對父子關系中涉及的所有人都擁有一個共同的祖先（這個祖先出現在這N對父子關系中），他需要對于小Hi的若幹次提問——每次提問為兩個人的名字（這兩個人的名字在之前的父子關系中出現過），告訴小Hi這兩個人的所有共同祖先中輩分最低的一個是誰？
提示：最近公共祖先無非就是兩點連通路徑上高度最小的點嘛！
輸入
每個測試點（輸入檔案）有且僅有一組測試資料。
每組測試資料的第1行為一個整數N，意義如前文所述。
每組測試資料的第2~N+1行，每行分别描述一對父子關系，其中第i+1行為兩個由大小寫字母組成的字元串Father_i, Son_i，分别表示父親的名字和兒子的名字。
每組測試資料的第N+2行為一個整數M，表示小Hi總共詢問的次數。
每組測試資料的第N+3~N+M+2行，每行分别描述一個詢問，其中第N+i+2行為兩個由大小寫字母組成的字元串Name1_i, Name2_i，分别表示小Hi詢問中的兩個名字。
對于100%的資料，滿足N<=10^5，M<=10^5, 且資料中所有涉及的人物中不存在兩個名字相同的人（即姓名唯一的确定了一個人），所有詢問中出現過的名字均在之前所描述的N對父子關系中出現過，且每個輸入檔案中第一個出現的名字所确定的人是其他所有人的公共祖先。
輸出
對于每組測試資料，對于每個小Hi的詢問，按照在輸入中出現的順序，各輸出一行，表示查詢的結果：他們的所有共同祖先中輩分最低的一個人的名字。
樣例輸入
4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin 樣例輸出
Sam
Adam
Adam #include <bits/stdc++.h>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
int n,_n,m,s;
struct EDGE
{
int to;
EDGE* las;
}e[1100001];
EDGE* last[1100001];
map<string,int>G;
string g[1100001];
int sx[1100001];
int f[30][1100001];
int deep[1100001];
int r[1100001];
int min(int x,int y)
{
return deep[x]<deep[y]?x:y;
}
void dfs(int t,int fa,int de)
{
sx[++_n]=t;
r[t]=_n;
deep[t]=de;
EDGE*ei;
for (ei=last[t];ei;ei=ei->las)
if (ei->to!=fa)
{
dfs(ei->to,t,de+1);
sx[++_n]=t;
}
}
int query(int l,int r)
{
if (l>r)
{
l^=r;
r^=l;
l^=r;
}
int k=int(log2(r-l+1));
return min(f[k][l],f[k][r-(1<<k)+1]);
}
int main()
{
scanf("%d",&n);
int j=0,x,y;
char x1[110],y1[110];
int ans=1;
for (int i=1;i<=n;++i)
{
cin>>x1>>y1;
if(!G[x1])
{
G[x1]=ans;
x=ans;
g[ans]=x1;
ans++;
}
else{x=G[x1];}
if(!G[y1])
{
G[y1]=ans;
y=ans;
g[ans]=y1;
ans++;
}
else {y=G[y1];}
//cout<<x<<" "<<y<<endl;
e[++j]={y,last[x]};
last[x]=e+j;
e[++j]={x,last[y]};
last[y]=e+j;
}
dfs(1,0,0);
for (int i=1;i<=_n;++i)f[0][i]=sx[i];
int ni=int(log2(_n)),nj,tmp;
for (int i=1;i<=ni;++i)
{
nj=_n+1-(1<<i);
tmp=1<<i-1;
for (j=1;j<=nj;++j)
f[i][j]=min(f[i-1][j],f[i-1][j+tmp]);
}
cin>>m;
while (m--)
{
cin>>x1>>y1;
x=G[x1];
y=G[y1];
//cout<<x<<" "<<y<<endl;
int su=query(r[x],r[y]);
//cout<<su<<endl;
cout<<g[su]<<endl;
}
}