弗洛伊德算法 $O(n^3)$ 哦? 可以过?!!! ```cpp #include <cstdio> #include <vector> #include <functional> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); vector<vector<char>> G(n, vector<char>(n, 0)); vector<int> w(n); for (int i = 1; i < n; ++i) { int x, y; scanf("%d %d", &x, &y); --x, --y; G[x][y] = 1; G[y][x] = 1; ++w[x], ++w[y]; } const int inf = 1e9; vector<vector<int>> f(n, vector<int>(n, inf)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (G[i][j]) f[i][j] = w[i]; } } for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i == j || i == k || j == k) continue; if (f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j]; } } } for (int i = 0; i < m; ++i) { int x, y; scanf("%d %d", &x, &y); --x, --y; printf("%d\n", (f[x][y] == inf ? 0 : f[x][y]) + w[y]); } return 0; } ``` 正解 最近公共祖先 ```cpp #include <cstdio> #include <vector> #include <tuple> #include <functional> using namespace std; int getBit(int x) { int res = 0; while (x) { ++res; x >>= 1; } return res; } int main() { int n, m; scanf("%d %d", &n, &m); int n_bit = getBit(n); // 父节点, 路径权和 vector<vector<tuple<int, int>>> f(n, vector<tuple<int, int>>(n_bit, make_tuple(-1, 0))); vector<vector<int>> G(n); vector<int> w(n), h(n); for (int i = 1; i < n; ++i) { int x, y; scanf("%d %d", &x, &y); --x, --y; G[y].push_back(x); G[x].push_back(y); ++w[x], ++w[y]; } function<void(int, int)> dfs = [&](int i, int pa) { // printf("%d -> %d\n", i, pa); for (int it : G[i]) { if (it != pa) { h[it] = h[i] + 1; f[it][0] = make_tuple(i, w[it]); dfs(it, i); } } }; dfs(0, -1); // dp for (int b = 1; b < n_bit; ++b) { for (int i = 0; i < n; ++i) { auto it = f[i][b - 1]; if (get<0>(it) != -1) { f[i][b] = make_tuple( get<0>(f[get<0>(it)][b - 1]), get<1>(it) + get<1>(f[get<0>(it)][b - 1]) ); } } } function<int(int, int)> lac = [&](int a, int b) { if (h[a] > h[b]) { int tmp = b; b = a; a = tmp; } int res = 0; // b 是更深的 int dh = h[b] - h[a], bit = 0; while (dh) { if (dh & 1) { res += get<1>(f[b][bit]); b = get<0>(f[b][bit]); } ++bit; dh >>= 1; } if (a == b) return res + w[a]; // ! for (int bb = n_bit - 1; bb >= 0; --bb) { if (get<0>(f[a][bb]) != get<0>(f[b][bb])) { res += get<1>(f[a][bb]) + get<1>(f[b][bb]); a = get<0>(f[a][bb]); b = get<0>(f[b][bb]); } } // printf("[%d] (%d, %d) - ", res, get<1>(f[a][0]), get<1>(f[b][0])); return res + get<1>(f[a][0]) + get<1>(f[b][0]) + w[get<0>(f[a][0])]; }; while (m--) { int u, v; scanf("%d %d", &u, &v); --u, --v; printf("%d\n", lac(u, v)); } return 0; } ```