結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2023-06-02 21:44:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,767 ms / 4,000 ms |
コード長 | 2,270 bytes |
コンパイル時間 | 4,455 ms |
コンパイル使用メモリ | 259,348 KB |
最終ジャッジ日時 | 2025-02-13 17:58:33 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001struct lca{vector<int> depth;vector<vector<int>> parents;int max_j=18;lca(int n,vector<vector<int>> &E){rep(i,100){if((1<<i)>E.size()){max_j = i;break;}}depth.assign(E.size(),-1);parents.assign(E.size(),vector<int>(max_j,-1));stack<int> s;s.push(n);depth[n] = 0;while(s.size()!=0){int k = s.top();s.pop();for(int i=0;i<E[k].size();i++){int x = E[k][i];if(depth[x]!=-1)continue;s.push(x);depth[x] = depth[k]+1;for(int j=0;j<max_j;j++){if(j==0){parents[x][j] = k;}else{parents[x][j] = parents[parents[x][j-1]][j-1];}if(parents[x][j] == -1)break;}}}}int kth_parent(int u,int k){for(int i=0;i<max_j;i++){if(k==0)break;if(u==-1)break;if(k%2){u = parents[u][i];}k/=2;}return u;}int query(int u,int v){if(depth[u]<depth[v])swap(u,v);u = kth_parent(u,depth[u]-depth[v]);if(u==v){return u;}for(int i=max_j-1;i>=0;i--){if(parents[u][i]!=parents[v][i]){u = parents[u][i];v = parents[v][i];}}return parents[u][0];}int get_distance(int u,int v){return depth[u]+depth[v]-2*depth[query(u,v)];}};vector<int> sz;void dfs(int cv,int pv,vector<vector<int>> &E){sz[cv] = 1;rep(i,E[cv].size()){int to = E[cv][i];if(to==pv)continue;dfs(to,cv,E);sz[cv] += sz[to];}}int main(){int n,q;cin>>n>>q;vector<vector<int>> E(n);rep(i,n-1){int a,b;cin>>a>>b;a--,b--;E[a].push_back(b);E[b].push_back(a);}lca L(0,E);sz.resize(n);dfs(0,-1,E);rep(_,q){int a,b;cin>>a>>b;a--,b--;int d =L.get_distance(a,b);if(d%2==1){cout<<0<<endl;continue;}if(L.depth[a]<L.depth[b])swap(a,b);int c = L.kth_parent(a,d/2);if(L.query(a,b)!=c){cout<<sz[c] - sz[L.kth_parent(a,d/2 - 1)]<<endl;}else{cout<<n - sz[L.kth_parent(a,d/2-1)] - sz[L.kth_parent(b,d/2-1)]<<endl;}}return 0;}