【hihoCoder第十七周】最近公共祖先·三

之前就写的是离线算法。思路就是先序一遍树，记录层数，然后高效RMQ就好。ST和线段树都能过。

以后有时间将之前的在线算法补上。

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100005

#define MAXM 105

#define inf 0x7ffffff

int n;

struct Edge {

    int v, next;

} edge[MAXN];

int head[MAXN];

int e;

void addEdge(int u, int v) { //加边

    edge[e].v = v;

    edge[e].next = head[u];

    head[u] = e++;

}

int first[MAXN];//结点在搜索顺序数组中最先出现的位置（下标）

int occur[MAXN << ]; //结点在出现的顺序数组重复的也要记录

int depth[MAXN << ]; //结点在搜索树中的深度，与occur相对应

int dp_min[MAXN << ][]; //dp_min[i][j] 表示从第i个位置开始的2^j个元素中的最小值的下标

int m = ; //不断记录出现的下标

void dfs(int u, int deep) {

    occur[++m] = u; //进入该点时进行记录

    depth[m] = deep;

    if(!first[u])

        first[u] = m;

    for(int i = head[u]; i + ; i = edge[i].next) {

        dfs(edge[i].v, deep + );

        occur[++m] = u; //访问子树返回也要标记

        depth[m] = deep;

    }

}

void init() {

    memset(head, -, sizeof(head));

    e = ;

}

void RMQ_init(int num) {

    for(int i = ; i <= num; i++)

        dp_min[i][] = i; //注意dp_min存的不是最小值，而是最小值的下标

    for(int j = ; j < ; j++)

        for(int i = ; i <= num; i++) {

            if(i + ( << j) -  <= num) {

                dp_min[i][j] = depth[dp_min[i][j - ]] < depth[dp_min[i + ( << (j - ))][j - ]] ? dp_min[i][j - ] : dp_min[i + ( << (j - ))][j - ];

            }

        }

}

int RMQ_min(int a, int b) {

    int l = first[a], r = first[b]; //得到区间左右端点

    if(l > r) {

        int t = l;

        l = r;

        r = t;

    }

    int k = (int)(log(double(r - l + )) / log(2.0));

    int min_id = depth[dp_min[l][k]] < depth[dp_min[r - ( << k) + ][k]] ? dp_min[l][k] : dp_min[r - ( << k) + ][k]; //最小值下标

    return occur[min_id];//取得当前下标表示的结点

}

map<string, int> Hash_zh;

map<int, string> Hash_fa;

int main() {

    int t, a, b;

    init();

    m = ;

    memset(first, , sizeof(first));

    bool in[MAXN];//记录结点有无入度

    memset(in, false, sizeof(in));

    int u = , v = , cnt = ;

    string str_u, str_v;

    scanf("%d", &n);

    for(int i = ; i <= n; i++) { //注意此题只有n-1条边

        cin >> str_u >> str_v;

        if (Hash_zh[str_u] == ) {

            Hash_fa[cnt] = str_u;

            Hash_zh[str_u] = cnt ++;

        }

        if (Hash_zh[str_v] == ) {

            Hash_fa[cnt] = str_v;

            Hash_zh[str_v] = cnt ++;

        }

        u = Hash_zh[str_u];

        v = Hash_zh[str_v];

        addEdge(u, v); //u->v单向

        //in[v] = true;

    }

    dfs(, );

    RMQ_init(m);

    int op_n;

    scanf ("%d", &op_n);

    while (op_n --) {

        cin >> str_u >> str_v;

        if (str_u == str_v) {

            cout << str_u << endl;

            continue;

        }

        u = Hash_zh[str_u];

        v = Hash_zh[str_v];

        cout << Hash_fa[RMQ_min(u, v)] << endl;

    }

    return ;

}