結果

問題 No.2337 Equidistant
ユーザー srjywrdnprktsrjywrdnprkt
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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);
//vLevel x ancestor
const 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;
};
//uvLCA
auto 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;
};
/*
ST
ST
d(1, S) < d(1, T)
x = d(S, T) (x % 2 == 0)
(Tlevel x/2 ancestor-(Tlevel x/2-1 ancestor)
d(1, S) = d(1, T)
N-(Tlevel x/2-1 ancestor)-(Slevel 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0