結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2023-06-02 22:59:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,818 ms / 4,000 ms |
コード長 | 3,621 bytes |
コンパイル時間 | 5,339 ms |
コンパイル使用メモリ | 261,452 KB |
実行使用メモリ | 80,572 KB |
最終ジャッジ日時 | 2024-12-28 21:28:44 |
合計ジャッジ時間 | 25,527 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;struct LCA{int n,m,cnt;vector<vector<int> > data,e;vector<int> depth,vis;LCA(int n):n(n){int ni = 1;cnt = 0;while(ni<n){ni<<=1;cnt++;}data = vector<vector<int> >(n,vector<int>(cnt+1,-1));e = vector<vector<int> >(n);depth = vector<int>(n,-1);}void addedge(int a,int b){e[a].push_back(b);e[b].push_back(a);}void dfs(int ni,int p,int now){depth[ni] = now;data[ni][0] = p;vis[ni] = 1;for(int to:e[ni]) if(to!=p){dfs(to,ni,now+1);}}void build(int root = 0){vis = vector<int> (n,0);dfs(root,-1,0);for(int i = 0;i<n;i++) if(vis[i]==0) dfs(i,-1,0);for(int i = 1;i<=cnt;i++){for(int j = 0;j<n;j++){data[j][i] = data[j][i-1];if(data[j][i]==-1) continue;data[j][i] = data[data[j][i]][i-1];}}}int query(int a,int b){if(depth[a] > depth[b]) swap(a,b);int need = depth[b] - depth[a];int nj = 0;while (need!=0){if(need&1) b = data[b][nj];nj++;need >>= 1;}if(a==b) return a;int now = cnt;while(now>=0){if(data[a][now]!=data[b][now]){a = data[a][now];b = data[b][now];}now--;}return data[a][0];}int dist(int a,int b){int c = query(a,b);return depth[a] + depth[b] - 2*depth[c];}int get(int i,int k){int j = i;int now = 0;while(k){if(k&1) j = data[j][now];if(j==-1) return j;k>>=1;now++;}return j;}};int n,q;vector<int> g[2<<17];vector<int> sz[2<<17];int nn[2<<17];int d1(int ni,int p){sort(g[ni].begin(),g[ni].end());nn[ni]++;sz[ni] = vector<int>(g[ni].size(),0);for(int i = 0;i<g[ni].size();i++){if(g[ni][i]==p) continue;sz[ni][i] = d1(g[ni][i],ni);nn[ni] += sz[ni][i];}return nn[ni];}int d2(int ni,int p,int now){if(p!=-1) nn[ni] += now;for(int i = 0;i<g[ni].size();i++){if(g[ni][i]==p){sz[ni][i] = now;continue;}d2(g[ni][i],ni,nn[ni]-sz[ni][i]);}return 0;}int main(){cin>>n>>q;LCA lca(n);for(int i = 0;i<n-1;i++){int u,v;cin>>u>>v;u--;v--;g[u].push_back(v);g[v].push_back(u);lca.addedge(u,v);}d1(0,-1);d2(0,-1,0);lca.build();while(q--){int x,y;cin>>x>>y;x--;y--;int t = lca.query(x,y);int dd = lca.dist(x,y);if(dd%2==1){cout<<0<<endl;continue;}int nx = lca.get(x,dd/2);int ny = lca.get(y,dd/2);if(ny!=-1&&lca.dist(t,ny)+lca.dist(ny,y)==lca.dist(t,y)){swap(nx,ny);swap(x,y);}int ans = n;int i = lca.get(x,dd/2-1);int j = 0;if(nx==t){j = lca.get(y,dd/2-1);}else{j = lca.get(nx,1);}int ni = lower_bound(g[nx].begin(),g[nx].end(),i) - g[nx].begin();int nj = lower_bound(g[nx].begin(),g[nx].end(),j) - g[nx].begin();ans -= sz[nx][ni] + sz[nx][nj];cout<<ans<<endl;}}