結果
問題 | No.2337 Equidistant |
ユーザー | hiro71687k |
提出日時 | 2023-06-02 22:30:25 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,903 ms / 4,000 ms |
コード長 | 5,103 bytes |
コンパイル時間 | 3,097 ms |
コンパイル使用メモリ | 219,176 KB |
実行使用メモリ | 120,996 KB |
最終ジャッジ日時 | 2024-06-09 00:00:42 |
合計ジャッジ時間 | 26,825 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 8 ms
5,376 KB |
testcase_07 | AC | 9 ms
5,376 KB |
testcase_08 | AC | 9 ms
5,376 KB |
testcase_09 | AC | 8 ms
5,376 KB |
testcase_10 | AC | 9 ms
5,376 KB |
testcase_11 | AC | 1,120 ms
106,572 KB |
testcase_12 | AC | 1,123 ms
106,704 KB |
testcase_13 | AC | 1,118 ms
106,596 KB |
testcase_14 | AC | 1,103 ms
106,476 KB |
testcase_15 | AC | 1,102 ms
106,472 KB |
testcase_16 | AC | 1,094 ms
106,616 KB |
testcase_17 | AC | 1,078 ms
106,632 KB |
testcase_18 | AC | 1,081 ms
106,708 KB |
testcase_19 | AC | 1,110 ms
106,568 KB |
testcase_20 | AC | 1,096 ms
106,516 KB |
testcase_21 | AC | 1,339 ms
120,996 KB |
testcase_22 | AC | 859 ms
106,900 KB |
testcase_23 | AC | 1,004 ms
107,512 KB |
testcase_24 | AC | 1,803 ms
115,812 KB |
testcase_25 | AC | 1,064 ms
107,480 KB |
testcase_26 | AC | 1,903 ms
115,624 KB |
testcase_27 | AC | 1,061 ms
107,396 KB |
testcase_28 | AC | 1,076 ms
107,404 KB |
ソースコード
#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{ ll now,y; if (a>b) { now=s,y=(a+b)/2; }else{ now=t,y=(b+a)/2; } ll nn=now; for (ll j = 0; j < 30; j++) { if (y&two[j]) { now=db[now][j]; } } y--; for (ll j = 0; j < 30; j++) { if (y&two[j]) { nn=db[nn][j]; } } ans.push_back(m[now]-m[nn]); } } for (ll i = 0; i < ans.size(); i++) { cout << ans[i] << endl; } }