HiHo一下 Week17 最近公共祖先 在线算法

HiHo

描述

上上回说到，小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

思路

这次采用的是在线算法了。
这种解法的关键在于在线性时间内将LCA问题转化为RMQ问题，然后就可以用ST算法解决，关于如何用ST解决RMQ问题，在Week17中说过，比较简单，所以这里只写如何化归。
首先LCA问题的主题是树，而RMQ问题的主题是数组；LCA求两个节点的公共祖先，RMQ求数组区间的最值；那么很容易就能想到，将树化为数组，两个节点化作数组区间的两个端点，使求祖先化为求最值。
如何实现呢？树的序列化方法无非就是各种遍历，这里用后序遍历，每次经过某节点时都记录到数组中（无论是从父节点来，还是从子节点归都算经过），同时附加上该节点的深度。记录下每个节点在数组中第一次出现的位置，那么对于要查询祖先的两个节点，这个祖先就是这两个位置中深度最浅的节点了。
现在算算复杂度，对于有n条边的树，回归为的数组长度应该是2n，那么ST算法构建的复杂度为$O(nlogn)$,每次查询为$O(1)$,加上n次查询，$O(nlogn+n)=O(nlogn)$，这个复杂度还是可以在规定时间内解决这种规模的问题的。

代码

#include<iostream>
using namespace std;
#include<string>
#include<algorithm>
#include<string.h>
#include<vector> 
#include<map>
#define MAX 100005
std::map<string,int> name;
string seekName[MAX];
std::vector<int> tree[MAX];
int minValue[20][2*MAX];
int minPos[20][2*MAX];
int fakeindex = 1, arrow = 1, n, d = 1;
int st[2*MAX];
int deep[2*MAX];
int pos[MAX];
//建树，通过邻接链表，vector::tree[i]存储i节点所连的边的编号
void buildTree(){
    cin >> n;
    for(int i=0;i<n;i++){
        string a,b;
        cin >> a;
        cin >> b;
        std::map<string,int>::iterator itA;
        std::map<string,int>::iterator itB;
        itA = name.find(a);
        if(itA == name.end()) {
            seekName[fakeindex] = a;
            name[a] = fakeindex++;
            itA = name.find(a);
        }
        itB = name.find(b);
        if(itB == name.end()) {
            seekName[fakeindex] = b;
            name[b] = fakeindex++;
            itB = name.find(b);
        }
        tree[itA->second].push_back(itB->second);
    }
}
//通过DFS将树转化为数组，以便划归为RMQ问题
void DFS(int x){
    deep[arrow] = d++;
    pos[x] = arrow;
    st[arrow++] = x;    
    for(int i=0;i<tree[x].size();i++){
        DFS(tree[x][i]);
        deep[arrow] = d-1;
        st[arrow++] = x;
    }
    d--;
}
//初始化ST数组，并计算出minValue和minPos
void initST(){
    for(int i=1;i<arrow;i++){
        minValue[0][i] = deep[i];
        minPos[0][i] = st[i];
    }
    int f = 1;
    for(int i=1;;i++)   {
        f = 1<<(i - 1);
        int len = arrow - (1<<i) + 1;
        if(len < 0) break;
        for(int j=1;j<=len;j++){
            if(minValue[i-1][j]<minValue[i-1][j + f]){
                minValue[i][j] = minValue[i-1][j];
                minPos[i][j] = minPos[i-1][j];
            }else{
                minValue[i][j] = minValue[i-1][j + f];
                minPos[i][j] = minPos[i-1][j + f];
            }           
        }
    }
}
//对于每个查询进行输出
void output(){
    int m;
    cin >> m;
    for(int k=0;k<m;k++){
        string a;
        string b;
        cin >> a;
        cin >> b;
        std::map<string,int>::iterator itA;
        std::map<string,int>::iterator itB;
        itA = name.find(a);
        itB = name.find(b);
        int l,r;
        l = pos[itA->second];
        r = pos[itB->second];
        if (l>r) swap(l,r);
        int len = r - l + 1;
        int j=0;while((1<<j)<=len)j++;j--;
        r = r - (1 << j) + 1; 
        int ans;
        if(minValue[j][l]<minValue[j][r]){
             ans = minPos[j][l];
        }else{
             ans = minPos[j][r];
        }
        cout << seekName[ans]<<endl;
    }
}
int main(){
    buildTree();
    //for(int i=1;i<fakeindex;i++) cout << i<<": "<<seekName[i]<<"   ";
    //cout << endl; 
    DFS(1);
    //for (int i=1;i<arrow;i++) cout<<st[i]<<" ";
    //cout <<endl;
    //for (int i=1;i<arrow;i++) cout<<deep[i]<<" ";
    //cout << endl;
    initST();
    output();
    return 0;
    }