結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2024-10-19 22:33:43 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 918 ms / 4,000 ms |
コード長 | 3,087 bytes |
コンパイル時間 | 3,114 ms |
コンパイル使用メモリ | 214,148 KB |
実行使用メモリ | 59,100 KB |
最終ジャッジ日時 | 2024-10-19 22:34:05 |
合計ジャッジ時間 | 18,219 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);ll N, A, B, Q, S, T, U, x;cin >> N >> Q;vector<vector<ll>> E(N);for (int i=0; i < N-1; i++){cin >> A >> B;A--; B--;E[A].push_back(B);E[B].push_back(A);}//部分木のサイズvector<int> subt(N);auto subtree_size=[&](auto self, int from, int p)->void{subt[from]=1;for (auto to : E[from]){if (to == p) continue;self(self, to, from); subt[from] += subt[to];}};subtree_size(subtree_size, 0, -1);//根からの距離vector<ll> dist(N);auto depth=[&](auto self, int from, int p)->void{for (auto to : E[from]){if (to == p) continue;dist[to] = dist[from]+1;self(self, to, from);}};depth(depth, 0, -1);//vのLevel x ancestorconst int LOG=20;vector par(LOG, vector<ll>(N, -1));auto ancestor=[&](auto self, int from, int p)->void{for (auto to : E[from]){if (to == p) continue;par[0][to] = from;self(self, to, from);}};ancestor(ancestor, 0, -1);for (int i=1; i<LOG; i++){for (int j=0; j<N; j++){if (par[i-1][j] != -1) par[i][j] = par[i-1][par[i-1][j]];}}auto la=[&](int v, int x)->int{for (int i=0; i<LOG; i++){if (x & (1<<i) && v != -1) v = par[i][v];}return v;};//uとvのLCAauto lca=[&](int u, int v)->int{if (dist[u] > dist[v]) swap(u, v);v = la(v, dist[v]-dist[u]);if (u == v) return u;for (int i=LOG-1; i>=0; i--){if (par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];}return par[0][u];};auto distance=[&](int u, int v)->int{return dist[u]+dist[v]-dist[lca(u, v)]*2;};/*SとTを結ぶパスの中心の点の子のうち、S、Tの部分木に含まれないものd(1, S) < d(1, T)のとき、x = d(S, T)として (x % 2 == 0)(Tのlevel x/2 ancestorの子の数-(Tのlevel x/2-1 ancestorの子の数)d(1, S) = d(1, T)のとき、N-(Tのlevel x/2-1 ancestorの子の数)-(Sのlevel x/2-1 ancestorの子の数)*/while(Q--){cin >> S >> T;S--; T--;x = distance(S, T);if (x % 2 == 1) cout << 0 << endl;else{ll ans=0;x /= 2;if (dist[S] == dist[T]){ans += N;U = la(S, x-1);ans -= subt[U];U = la(T, x-1);ans -= subt[U];}else{if (dist[S] > dist[T]) swap(S, T);U = la(T, x);ans += subt[U];U = la(T, x-1);ans -= subt[U];}cout << ans << endl;}}return 0;}