Hdu4547CD操作离线lca

题意：根目录能一次到达其任意子目录，子目录返回上一层目录需要一次，给出目录关系，问从某个目录到某个目录最少要多少步。

操作数 ，就是起点到最近公共祖先的距离。

然后讨论下，如果最近公共祖先等于终点，那么答案就是起点到祖先的高度差 ，否则就是高度差加一 。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<string>
using namespace std;

const int maxn = 111111;

int father[maxn];

map<pair<int, int>, int> ans;
vector<int> q[maxn];
int getfather(int x)
{
    if (father[x] != x) return father[x] = getfather(father[x]);
    return father[x];
}
int len, head[maxn];
int l[maxn], r[maxn];
struct Node
{
    int to; int next;
}e[maxn * 2];
int deep[maxn];
int color[maxn];
void add(int from, int to)
{
    e[len].to = to;
    e[len].next = head[from];
    head[from] = len++;
}

int un(int x, int y)
{
    int fx = getfather(x); int fy = getfather(y);
    father[fy] = fx;
}

void dfs(int x)
{
    for (int i = head[x]; i != -1; i = e[i].next){
        int cc = e[i].to;
        dfs(cc);
        un(x, cc);
    }
    color[x] = 1;
    for (int i = 0; i < q[x].size(); i++){
        int t = q[x][i];
        if (color[t]){
            int gg = getfather(t);
            ans[make_pair(x, t)] = gg;
            ans[make_pair(t, x)] = gg;
        }
    }
}

void build(int root, int dep)
{
    deep[root] = dep;
    for (int i = head[root]; i != -1; i = e[i].next){
        int cc = e[i].to;
        build(cc, dep + 1);
    }
}
int gg[maxn];
void init(int n)
{
    len = 0;
    memset(head, -1, sizeof(head));
    memset(color, 0, sizeof(color));
    memset(gg, 0, sizeof(gg));
    for (int i = 1; i <= n; i++)
        father[i] = i;
    for (int i = 1; i <= n; i++)
        q[i].clear();

}

int main()
{
    int T;
    int n, M;
    char a[100], b[100];
    cin >> T;
    map<string, int> m;
    while (T--){
        int cnt = 1;
        m.clear();
        scanf("%d%d", &n, &M);
        init(n);
        for (int i = 0; i < n - 1; i++){
            scanf("%s%s", a, b); int c; int d;
            if (!m[a]) m[a] = cnt++;
            if (!m[b]) m[b] = cnt++;
            c = m[a]; d = m[b];
            add(d, c); gg[c] = 1;
        }
        int root;
        for (int i = 1; i <= n; i++)
        if (!gg[i]){
            root = i; break;
        }
        build(root, 1);
        for (int i = 0; i < M; i++){
            scanf("%s%s", a, b);
            int c = m[a]; int d = m[b];
            l[i] = c; r[i] = d;
            q[c].push_back(d);
            q[d].push_back(c);
        }
        dfs(root);
        for (int i = 0; i < M; i++){
            int t = ans[make_pair(l[i], r[i])];
            if (t == r[i]){
                printf("%d
", deep[l[i]] - deep[t]);
            }
            else{
                printf("%d
", deep[l[i]] - deep[t] + 1);
            }
        }
    }
    return 0;
}