結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2023-06-02 22:15:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,558 bytes |
コンパイル時間 | 2,288 ms |
コンパイル使用メモリ | 209,392 KB |
最終ジャッジ日時 | 2025-02-13 18:41:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 WA * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll=long long;using ld=long double;ld pie=3.141592653589793;ll inf=2000000000000000000;ll mod=998244353;/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体query(u,v): u と v の LCA を求める。計算量 O(logn)前処理: O(nlogn)時間, O(nlogn)空間*/struct LCA {vector<vector<long long>> parent; // parent[k][u]:= u の 2^k 先の親vector<ll> dist; // root からの距離LCA(vector<vector<ll>> &G, ll root = 0) { init(G, root); }// 初期化void init(vector<vector<ll>> &G, int root = 0) {ll V = G.size();int K = 1;while ((1 << K) < V) K++;parent.assign(K, vector<ll>(V, -1));dist.assign(V, -1);dfs(G, root, -1, 0);for (int k = 0; k + 1 < K; k++) {for (int v = 0; v < V; v++) {if (parent[k][v] < 0) {parent[k + 1][v] = -1;} else {parent[k + 1][v] = parent[k][parent[k][v]];}}}}// 根からの距離と1つ先の頂点を求めるvoid dfs(vector<vector<ll>> &G, int v, int p, int d) {parent[0][v] = p;dist[v] = d;for (auto e : G[v]) {if (e != p) dfs(G, e, v, d + 1);}}int query(int u, int v) {if (dist[u] < dist[v]) swap(u, v); // u の方が深いとするint K = parent.size();// LCA までの距離を同じにするfor (int k = 0; k < K; k++) {if ((dist[u] - dist[v]) >> k & 1) {u = parent[k][u];}}// 二分探索で LCA を求めるif (u == v) return u;for (int k = K - 1; k >= 0; k--) {if (parent[k][u] != parent[k][v]) {u = parent[k][u];v = parent[k][v];}}return parent[0][u];}};ll dfs(ll now,vector<ll>&m,vector<vector<ll>>&g){m[now]=-1;ll x=1;for (ll i = 0; i < g[now].size(); i++){if (m[g[now][i]]==-1){continue;}x+=dfs(g[now][i],m,g);}m[now]=x;return x;}int main(){ll n,q;cin >> n >> q;vector<vector<ll>>g(n);for (ll i = 0; i < n-1; i++){ll a,b;cin >> a >> b;a--,b--;g[a].push_back(b);g[b].push_back(a);}vector<ll>m(n,0);dfs(0,m,g);queue<ll>que;vector<ll>memo(n,inf);memo[0]=0;que.push(0);while (!que.empty()){ll v=que.front();que.pop();for (ll i = 0; i < g[v].size(); i++){if (memo[g[v][i]]>memo[v]+1){memo[g[v][i]]=memo[v]+1;que.push(g[v][i]);}}}LCA lca(g,0);vector<ll>ans;vector<vector<ll>>db(n,vector<ll>(30,-1));for (ll i = 0; i < n; i++){for (ll j = 0; j < g[i].size(); j++){if (memo[g[i][j]]==memo[i]-1){db[i][0]=g[i][j];break;}}}for (ll j = 1; j < 30; j++){for (ll i = 0; i < n; i++){if (db[i][j-1]==-1){continue;}db[i][j]=db[db[i][j-1]][j-1];}}vector<ll>two(40,1);for (ll i = 1; i < 40; i++){two[i]=two[i-1]*2;}for (ll i = 0; i < q; i++){ll s,t;cin >> s >> t;s--,t--;ll x=lca.query(s,t);ll a=memo[s]-memo[x];ll b=memo[t]-memo[x];if (a%2!=b%2){ans.push_back(0);}else if (a==b){if (a==1){ans.push_back(n-m[s]-m[t]);continue;}a--;b--;ll xx=s;for (ll j = 0; j < 30; j++){if (a&two[j]){xx=db[xx][j];}}ll yy=t;for (ll j = 0; j < 30; j++){if (b&two[j]){yy=db[yy][j];}}ans.push_back(n-m[xx]-m[yy]);}else{ans.push_back(1);}}for (ll i = 0; i < ans.size(); i++){cout << ans[i] << endl;}}