没啥好说的。就是一个LCA。
不过就是有从根到子树里任意一个节点只需要一次操作，特判一下LCA是不是等于v。相等的话不用走。否则就是1次操作。
主要是想写一下倍增的板子。
倍增基于二进制。暴力求LCA算法是while循环一步一步往上走。但其实是不需要的。
因为一个点走到它的任意一个祖先都是确定的步数。都可用表示成二进制数。
$lca_{u,i}$代表从$u$向上走$2^{i}$步到哪一个节点
预处理出来。让$u$，$v$同深度，再向上走$x-1$步就好了($x$代表两$u, v$到它们LCA的深度差)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <string>
#include <iostream>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
}
const int N = 1e5 + ;
struct Edge { int v, next; } edge[N];
int n, m, cnt, head[N], fa[N], degree[N], lca[N][], dep[N];
bool vis[N];
map<string, int> mp;
int tol; inline void init() {
memset(head, , sizeof(head));
memset(fa, , sizeof(fa));
memset(vis, , sizeof(vis));
memset(degree, , sizeof(degree));
memset(lca, , sizeof(lca));
cnt = tol = ;
mp.clear();
} inline void addedge(int u, int v) {
edge[++cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt;
} int index(string s) {
if (mp.find(s) != mp.end()) return mp[s];
return mp[s] = ++tol;
} void dfs(int u) {
vis[u] = ;
lca[u][] = fa[u];
for (int i = ; i <= ; i++) lca[u][i] = lca[lca[u][i-]][i-];
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (vis[v]) continue;
dep[v] = dep[u] + ;
fa[v] = u;
dfs(v);
}
} int Lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = ; i >= ; i--) if (dep[lca[u][i]] >= dep[v]) u = lca[u][i];
if (u == v) return u;
for (int i = ; i >= ; i--) if (lca[u][i] != lca[v][i]) u = lca[u][i], v = lca[v][i];
return lca[u][];
} int main() {
int T = read();
while (T--) {
init();
n = read(); m = read();
for (int i = ; i < n - ; i++) {
string a, b;
cin >> a >> b;
int u = index(a), v = index(b);
addedge(v, u);
degree[u]++;
}
int root = ;
for (int i = ; i <= n; i++) if (!degree[i]) { root = i; break; }
fa[root] = root;
dfs(root);
while (m--) {
string a, b;
cin >> a >> b;
int u = index(a), v = index(b);
int r = Lca(u, v);
printf("%d\n", dep[u] - dep[r] + (v == r ? : ));
}
}
return ;
}
交了之后发现跑了两秒多
然后写了发tarjan的 跑了1秒多 果然 tarjan的时间复杂度还是最优的
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <string>
#include <iostream>
using namespace std; inline int read() {
int x = , f = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }
while (ch >= '' && ch <= '') { x = x * + ch - ; ch = getchar(); }
return x * f;
}
const int N = 1e5 + ;
struct Edge { int v, next; } edge[N];
int cnt, head[N];
inline void addedge(int u, int v) {
edge[++cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt;
}
struct Qedge { int v, next, num; } qedge[N * ];
int qcnt, qhead[N];
inline void addqedge(int u, int v, int num) {
qedge[++qcnt].v = v;
qedge[qcnt].next = qhead[u];
qhead[u] = qcnt;
qedge[qcnt].num = num;
}
int n, m, fa[N], degree[N], dep[N];
int ans[N];
bool vis[N];
map<string, int> mp;
int tol; inline void init() {
memset(head, , sizeof(head));
memset(qhead, , sizeof(qhead));
memset(fa, , sizeof(fa));
memset(vis, , sizeof(vis));
memset(degree, , sizeof(degree));
memset(dep, , sizeof(dep));
memset(ans, , sizeof(ans));
cnt = qcnt = tol = ;
mp.clear();
} int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); } int index(string s) {
if (mp.find(s) != mp.end()) return mp[s];
return mp[s] = ++tol;
} void dfs(int u) {
fa[u] = u;
vis[u] = ;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (vis[v]) continue;
dep[v] = dep[u] + ;
dfs(v);
fa[v] = u;
}
for (int i = qhead[u]; i; i = qedge[i].next) {
int v = qedge[i].v;
if (vis[v]) {
ans[qedge[i].num] = getfa(v);
}
}
} int main() {
int T = read();
while (T--) {
init();
n = read(); m = read();
for (int i = ; i < n - ; i++) {
string a, b;
cin >> a >> b;
int u = index(a), v = index(b);
addedge(v, u);
degree[u]++;
}
int root = ;
for (int i = ; i <= n; i++) if (!degree[i]) { root = i; break; }
for (int i = ; i <= m; i++) {
string a, b;
cin >> a >> b;
int u = index(a), v = index(b);
addqedge(u, v, i);
addqedge(v, u, i);
}
dep[root] = ;
dfs(root);
for (int i = ; i <= m; i++) {
int u = qedge[ * i].v, v = qedge[ * i - ].v;
printf("%d\n", dep[u] - dep[ans[i]] + (ans[i] == v ? : ));
}
}
return ;
}