链接：https://ac.nowcoder.com/acm/contest/549/F
来源：牛客网
小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的体力值是多少。
这张图可以认为是边权全为1的树上增加了一条边权为0的边。 首先先不考虑多出来的一条边，那么dep[u]表示点u的深度，任意两点u，v的最短的距离就是 dep[u]+dep[v]−2dep[lca(u,v)], 加上这条边后另外一种可能最短的路径就是经过这条边权为0的边，可以建图之后跑一次最短路，每次查询的答案都是 min(dis[u]+dis[v],dep[u]+dep[v]−2dep[lca(u,v)])。 #include <bits/stdc++.h> using namespace std; const int maxn = 2e6 + 5; int head[maxn], tot; struct Edge { int u, v, next; }edge[maxn]; int father[maxn], depth[maxn], size[maxn], son[maxn], top[maxn]; int L[maxn], R[maxn], Index; void init() { memset(head, -1, sizeof(head)); tot = 1; } void add(int u, int v) { edge[++tot].u = u; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot; } void dfs1(int u, int fa) { size[u] = 1; son[u] = 0; father[u] = fa; depth[u] = depth[fa] + 1; int maxson = -1; for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (to == fa) { continue; } dfs1(to, u); size[u] += size[to]; if (size[to] > maxson) { maxson = size[to]; son[u] = to; } } } void dfs2(int u, int topf) { top[u] = topf; L[u] = R[u] = ++Index; if (son[u]) { dfs2(son[u], topf); } for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (L[to] || to == son[u]) { continue; } dfs2(to, to); } R[u] = Index; } int LCA(int x, int y) { while (top[x] != top[y]) { if (depth[top[x]] < depth[top[y]]) { swap(x, y); } x = father[top[x]]; } if (depth[x] > depth[y]) { return y; } return x; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); int n, m, s, u, v; scanf("%d", &n); for (int i = 1; i <= n - 1; i++) { scanf("%d%d", &u, &v); add(u, v); add(v, u); } dfs1(1, 1); dfs2(1, 1); int a, b, c; scanf("%d%d", &a, &b); int x, y; scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &x, &y); int L1 = LCA(x, y); int L2 = LCA(x, a); int L3 = LCA(x, b); int L4 = LCA(y, a); int L5 = LCA(y, b); // cout << L1 << " " << L2 << " " << L3 << " " << L4 << " " << L5 << endl; int x1 = depth[x] + depth[y] - 2 * depth[L1]; int x2 = depth[x] + depth[a] - 2 * depth[L2]; int x3 = depth[y] + depth[b] - 2 * depth[L5]; int x4 = depth[x] + depth[b] - 2 * depth[L3]; int x5 = depth[y] + depth[a] - 2 * depth[L4]; // cout << x1 << " " << x2 << " " << x3 << " " << x4 << " " << x5 << endl; int tmp = min(x2 + x3, x4 + x5); printf("%d\n", min(tmp, x1)); } return 0; }
