本文共 2367 字，大约阅读时间需要 7 分钟。
题目链接：
思路：这题的本质还是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 #include #include #include #include #include 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 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;}
转载于:https://www.cnblogs.com/wally/p/4477049.html