結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2023-06-02 22:16:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 393 ms / 4,000 ms |
コード長 | 3,024 bytes |
コンパイル時間 | 2,159 ms |
コンパイル使用メモリ | 207,020 KB |
最終ジャッジ日時 | 2025-02-13 18:44:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll=long long;using pll=pair<ll,ll>;using tll=tuple<ll,ll,ll>;using ld=long double;const ll INF=(1ll<<60);#define rep(i,n) for (ll i=0;i<(ll)(n);i++)#define all(v) v.begin(),v.end()template<class T> void chmin(T &a,T b){if(a>b){a=b;}}template<class T> void chmax(T &a,T b){if(a<b){a=b;}}struct tree{int n,max_k=1;vector<vector<int>> g;vector<vector<int>> parent;vector<int> depth,sz;tree(int g_size){n=g_size;g.resize(n);}void add_edge(int u,int v){g[u].push_back(v);g[v].push_back(u);}void LCA(int root=0){while((1<<max_k)<n) max_k++;parent.assign(max_k,vector<int>(n,-1));depth.assign(n,-1);sz.assign(n,0);dfs(root,-1,0);for(int k=0;k+1<max_k;k++){for(int i=0;i<n;i++){if(parent[k][i]==-1){parent[k+1][i]=-1;}else{parent[k+1][i]=parent[k][parent[k][i]];}}}}void dfs(int v,int par,int d){parent[0][v]=par;depth[v]=d;sz[v]++;for(auto &i:g[v]){if(i!=par){dfs(i,v,d+1);sz[v]+=sz[i];}}}int get_lca(int u,int v){if(depth[u]<depth[v]) swap(u,v);int diff=depth[u]-depth[v];for(int k=0;k<max_k;k++){if(diff&(1<<k)){u=parent[k][u];}}if(u==v) return u;for(int k=max_k-1;0<=k;k--){if(parent[k][u]!=parent[k][v]){u=parent[k][u];v=parent[k][v];}}return parent[0][u];}int get_dist(int u,int v){return depth[u]+depth[v]-2*depth[get_lca(u,v)];}int on_path(int x,int u,int v){return get_dist(u,x)+get_dist(x,v)==get_dist(u,v);}ll d(ll s,ll diff){for(int k=0;k<max_k;k++){if(diff&(1<<k)){s=parent[k][s];}}return s;}ll q(ll s,ll t){if(depth[s]==depth[t]){ll u=get_lca(s,t);ll a=get_dist(s,u);ll b=get_dist(t,u);ll x=d(s,a-1);ll y=d(t,b-1);return n-sz[u]+sz[u]-sz[x]-sz[y];}ll k=get_dist(s,t);if(k%2!=0) return 0;if(depth[s]<depth[t]) swap(s,t);s=d(s,k/2-1);ll l=parent[0][s];return sz[l]-sz[s];}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);ll n,q;cin >> n >> q;tree g(n);rep(i,n-1){ll a,b;cin >> a >> b;a--;b--;g.add_edge(a,b);}g.LCA(0);while(q--){ll s,t;cin >> s >> t;s--;t--;ll ans=0;ans+=g.q(s,t);cout << ans << '\n';}}