結果

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

ソースコード

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

#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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0