結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2023-06-02 21:53:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 307 ms / 4,000 ms |
コード長 | 4,255 bytes |
コンパイル時間 | 2,345 ms |
コンパイル使用メモリ | 206,032 KB |
最終ジャッジ日時 | 2025-02-13 18:07:24 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=400005,INF=1<<30;struct HeavyLightDecomposition{int n;vector<int> sz,in,out,nxt,par,depth;vector<vector<int>> G;HeavyLightDecomposition(){}HeavyLightDecomposition(int n_){n=n_;sz.assign(n,0);in.assign(n,0);out.assign(n,0);nxt.assign(n,0);par.assign(n,0);depth.assign(n,0);G.assign(n,vector<int>());}void add_edge(int u,int v){G[u].push_back(v);G[v].push_back(u);}void dfs_sz(int u,int p){par[u]=p;sz[u]=1;if(G[u].size()&&G[u][0]==p) swap(G[u][0],G[u].back());for(auto &a:G[u]){if(a==p) continue;depth[a]=depth[u]+1;dfs_sz(a,u);sz[u]+=sz[a];if(sz[a]>sz[G[u][0]]){swap(a,G[u][0]);}}}void dfs_hld(int u,int p,int &t){in[u]=t++;for(auto a:G[u]){if(a==p) continue;nxt[a]=(a==G[u][0] ? nxt[u] : a);dfs_hld(a,u,t);}out[u]=t;}void build(int u){int t=0;dfs_sz(u,-1);dfs_hld(u,-1,t);}int lca(int u,int v){if(in[u]>in[v]) swap(u,v);if(nxt[u]==nxt[v]) return u;return lca(u,par[nxt[v]]);}int mov1(int a,int b){if(a==b) return a;int c=lca(a,b);if(c==a){int l=0,r=si(G[a]);while(r-l>1){int m=(l+r)/2;if(par[a]==G[a][m]){if(m+1<r){if(r-l==2){l=m+1;break;}if(in[G[a][m+1]]<=in[b]) l=m+1;else r=m;}else{if(r-l==2){l=m-1;break;}if(in[G[a][m-1]]<=in[b]) l=m-1;else r=m-1;}}else{if(in[G[a][m]]<=in[b]) l=m;else r=m;}}if(par[a]!=G[a][l]) return G[a][l];else return G[a][l+1];//return G[a][l];}else{return par[a];}}//aからbに向かって1進んだところ};//部分木クエリはquery(in[a],out[a])//点はquery(in[a],in[a]+1)int par[20][MAX];int main(){std::ifstream in("text.txt");std::cin.rdbuf(in.rdbuf());cin.tie(0);ios::sync_with_stdio(false);int N,Q;cin>>N>>Q;HeavyLightDecomposition hld(N);for(int i=0;i<N-1;i++){int a,b;cin>>a>>b;a--;b--;hld.add_edge(a,b);}hld.build(0);memset(par,-1,sizeof(par));for(int i=0;i<N;i++) par[0][i]=hld.par[i];for(int t=1;t<20;t++){for(int i=0;i<N;i++){if(par[t-1][i]!=-1) par[t][i]=par[t-1][par[t-1][i]];}}while(Q--){int a,b;cin>>a>>b;a--;b--;int c=hld.lca(a,b);int dis=hld.depth[a]+hld.depth[b]-2*hld.depth[c];if(dis&1){cout<<0<<"\n";continue;}if(hld.depth[a]<hld.depth[b]) swap(a,b);int x=a;for(int t=19;t>=0;t--){if((dis/2)&(1<<t)){x=par[t][x];}}int ans=N;if(x==c){ans-=hld.out[hld.mov1(x,a)]-hld.in[hld.mov1(x,a)];ans-=hld.out[hld.mov1(x,b)]-hld.in[hld.mov1(x,b)];}else{ans=hld.out[x]-hld.in[x];ans-=hld.out[hld.mov1(x,a)]-hld.in[hld.mov1(x,a)];}cout<<ans<<"\n";}}