题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4547

思路：这题的本质还是LCA问题，但是需要注意的地方有：

1、如果Q中u,v的lca为u，那么只需一步u->...->v。

2、如果Q中u,v的lca为v，那么需abs(dist[u]  - dist[v])步。

3、否则以上情况都不满足，那么需abs(dist[v] - dist[lca(u, v)])+1步。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <map>

using namespace std;

const int MAX_N = (400000 + 20000);

struct Edge {

    int v, next;

} edge[MAX_N];

int NE, cnt, head[MAX_N], Indegree[MAX_N];

map<string, int > mp;

void Init()

{

    mp.clear();

    cnt = NE = 0;

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

    memset(Indegree, 0, sizeof(Indegree));

}

void Insert(int u, int v)

{

    edge[NE].v = v;

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

    head[u] = NE++;

}

struct q_edge {

    int u, v, id, next;

} q_ee[MAX_N];

int q_ne, q_head[MAX_N];

void q_init()

{

    q_ne = 0;

    memset(q_head, -1, sizeof(q_head));

}

void q_insert(int u, int v, int id)

{

    q_ee[q_ne].u = u;

    q_ee[q_ne].v = v;

    q_ee[q_ne].id = id;

    q_ee[q_ne].next = q_head[u];

    q_head[u] = q_ne++;

}

int N, M, ans[MAX_N], dist[MAX_N];

int parent[MAX_N], lca[MAX_N];

bool vis[MAX_N];

int Find(int x)

{

    if (x == parent[x]) {

        return parent[x];

    }

    return parent[x] = Find(parent[x]);

}

void dfs(int u)

{

    parent[u] = u;

    vis[u] = true;

    for (int i = q_head[u]; ~i; i = q_ee[i].next) {

        int v = q_ee[i].v, id = q_ee[i].id;

        if (vis[v]) {

            lca[id] = Find(v);

        }

    }

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

        int v = edge[i].v;

        if (!vis[v]) {

            dist[v] = dist[u] + 1;

            dfs(v);

            parent[v] = u;

        }

    }

}

int main()

{

    int Cas;

    cin >> Cas;

    while (Cas--) {

        cin >> N >> M;

        Init();

        for (int i = 1; i < N; ++i) {

            string str1, str2;

            cin >> str1 >> str2;

            if (mp.find(str1) == mp.end()) mp[str1] = ++cnt;

            if (mp.find(str2) == mp.end()) mp[str2] = ++cnt;

            Indegree[mp[str1]]++;

            Insert(mp[str2], mp[str1]);

        }

        q_init();

        for (int i = 1; i <= M; ++i) {

            string str1, str2;

            cin >> str1 >> str2;

            q_insert(mp[str1], mp[str2], i);

            q_insert(mp[str2], mp[str1], i);

        }

        //from root;

        memset(vis, false, sizeof(vis));

        for (int i = 1; i <= cnt; ++i) {

            if (!Indegree[i]) {

                dist[i] = 0;

                dfs(i);

                break;

            }

        }

        for (int i = 0; i < q_ne; ++i) {

            if (!(i & 1)) {

                if (q_ee[i].u == q_ee[i].v) {

                    puts("0");

                } else if (q_ee[i].u == lca[q_ee[i].id]) {

                    puts("1");

                } else if (q_ee[i].v == lca[q_ee[i].id]) {

                    printf("%d\n", abs(dist[q_ee[i].v] - dist[q_ee[i].u]));

                } else {

                    printf("%d\n", abs(dist[q_ee[i].u] - dist[lca[q_ee[i].id]]) + 1);

                }

            }

        }

    }

    return 0;

}