結果
問題 |
No.2337 Equidistant
|
ユーザー |
![]() |
提出日時 | 2025-04-22 02:08:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,565 bytes |
コンパイル時間 | 2,568 ms |
コンパイル使用メモリ | 203,016 KB |
実行使用メモリ | 43,152 KB |
最終ジャッジ日時 | 2025-04-22 02:08:33 |
合計ジャッジ時間 | 22,431 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 WA * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<vector<int>> g(n); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } vector<int> sz(n), par(n), tin(n), tout(n), dep(n); int _t; auto dfs = [&] (auto&& self, int u, int p) -> void { dep[u] = dep[p] + 1; par[u] = p; sz[u] = 1; tin[u] = _t++; for (int v : g[u]) if (v != p) { self(self, v, u); sz[u] += sz[v]; } tout[u] = _t; }; dfs(dfs, 0, 0); int lg = __lg(n) + 1; vector table(lg, par); for (int p = 1; p < lg; p++) { for (int i = 0; i < n; i++) { table[p][i] = table[p - 1][table[p - 1][i]]; } } auto f_k = [&] (int u, int k) { for (int p = 0; p < lg; p++) { if (k >> p & 1) { u = table[p][u]; } } return u; }; auto lca = [&] (int u, int v) { if (dep[u] > dep[v]) swap(u, v); int d = dep[v] - dep[u]; for (int p = 0; p < lg; p++) { if (d >> p & 1) { v = table[p][v]; } } if (u == v) return u; for (int p = lg - 1; p >= 0; p--) { if (table[p][u] != table[p][v]) { u = table[p][u]; v = table[p][v]; } } return par[u]; }; while (q--) { int u, v; cin >> u >> v; --u, --v; if (dep[u] > dep[v]) swap(u, v); if (tin[u] <= tin[v] && tout[v] <= tout[u]) { // u is ancestor of v int dist = dep[v] - dep[u]; if (dist % 2) { cout << 0 << endl; continue; } int mid = f_k(v, dist / 2); int mid2 = f_k(v, dist / 2 - 1); cout << sz[mid] - sz[mid2] << endl; continue; } int l = lca(u, v); int du = dep[u] - dep[l]; int dv = dep[v] - dep[l]; int dist = du + dv; if (dist % 2) { cout << 0 << endl; continue; } if (du == dv) { int lu = f_k(u, du - 1); int lv = f_k(v, dv - 1); cout << sz[l] - sz[lu] - sz[lv] << endl; } else { int ref = (du > dv ? u : v); int mid = f_k(ref, dist / 2); int mid2 = f_k(ref, dist / 2 - 1); cout << sz[mid] - sz[mid2] << endl; } } }