結果
問題 | No.2337 Equidistant |
ユーザー |
|
提出日時 | 2023-06-02 22:32:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 631 ms / 4,000 ms |
コード長 | 1,133 bytes |
コンパイル時間 | 2,823 ms |
コンパイル使用メモリ | 169,172 KB |
実行使用メモリ | 49,664 KB |
最終ジャッジ日時 | 2024-12-28 20:03:07 |
合計ジャッジ時間 | 13,112 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;const int N=2e5+10;const int D=18;int f[N][D+1];int dep[N],sz[N];vector<int>e[N];int n,q,x,y;void dfs(int x,int y,int d){dep[x]=d;f[x][0]=y;sz[x]=1;for (int i=1;i<=D;i++) f[x][i]=f[f[x][i-1]][i-1];for (int i=0;i<e[x].size();i++){int u=e[x][i];if (u==y) continue;dfs(u,x,d+1);sz[x]+=sz[u];}}int get_lca(int x,int y){for (int i=D;i>=0;i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i];for (int i=D;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];if (x!=y) x=f[x][0];return x;}int up(int x,int y){for (int i=D;i>=0;i--) if ((y>>i)&1) x=f[x][i];return x;}void solve(int x,int y){if (dep[x]<dep[y]) swap(x,y);int lca=get_lca(x,y);int t=dep[x]+dep[y]-2*dep[lca];if (t&1) puts("0");else{if (dep[x]==dep[y]){printf("%d\n",n-sz[up(x,(t>>1)-1)]-sz[up(y,(t>>1)-1)]);}else{printf("%d\n",sz[up(x,t>>1)]-sz[up(x,(t>>1)-1)]);}}}int main(){scanf("%d%d",&n,&q);for (int i=1;i<n;i++){scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);}dfs(1,0,1);for (int i=1;i<=q;i++){scanf("%d%d",&x,&y);solve(x,y);}}