結果
問題 | No.2337 Equidistant |
ユーザー |
![]() |
提出日時 | 2022-08-22 19:23:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,273 ms / 4,000 ms |
コード長 | 3,905 bytes |
コンパイル時間 | 2,649 ms |
コンパイル使用メモリ | 208,964 KB |
最終ジャッジ日時 | 2025-01-31 02:52:37 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;#line 2 "graph/tree/doubling-lowest-common-ancestor.hpp"#line 2 "graph/graph-template.hpp"/*** @brief Graph Template(グラフテンプレート)*/template< typename T = int >struct Edge {int from, to;T cost;int idx;Edge() = default;Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}operator int() const { return to; }};template< typename T = int >struct Graph {vector< vector< Edge< T > > > g;int es;Graph() = default;explicit Graph(int n) : g(n), es(0) {}size_t size() const {return g.size();}void add_directed_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es++);}void add_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es);g[to].emplace_back(to, from, cost, es++);}void read(int M, int padding = -1, bool weighted = false, bool directed = false) {for(int i = 0; i < M; i++) {int a, b;cin >> a >> b;a += padding;b += padding;T c = T(1);if(weighted) cin >> c;if(directed) add_directed_edge(a, b, c);else add_edge(a, b, c);}}inline vector< Edge< T > > &operator[](const int &k) {return g[k];}inline const vector< Edge< T > > &operator[](const int &k) const {return g[k];}};template< typename T = int >using Edges = vector< Edge< T > >;#line 4 "graph/tree/doubling-lowest-common-ancestor.hpp"/*** @brief Doubling-Lowest-Common-Ancestor(最小共通祖先)* @docs docs/doubling-lowest-common-ancestor.md*/template< typename T >struct DoublingLowestCommonAncestor : Graph< T > {public:using Graph< T >::g;vector< int > dep;vector< int > sum;vector< vector< int > > table;const int LOG;explicit DoublingLowestCommonAncestor(int n): Graph< T >(n), LOG(32 - __builtin_clz(g.size())) {}explicit DoublingLowestCommonAncestor(const Graph< T > &g): LOG(32 - __builtin_clz(g.size())), Graph< T >(g) {}void build(int root = 0) {dep.assign(g.size(), 0);sum.assign(g.size(), 0);table.assign(LOG, vector< int >(g.size(), -1));dfs(root, -1, 0);for(int k = 0; k + 1 < LOG; k++) {for(int i = 0; i < (int)table[k].size(); i++) {if(table[k][i] == -1) table[k + 1][i] = -1;else table[k + 1][i] = table[k][table[k][i]];}}}int lca(int u, int v) {if(dep[u] > dep[v]) swap(u, v);v = climb(v, dep[v] - dep[u]);if(u == v) return u;for(int i = LOG - 1; i >= 0; i--) {if(table[i][u] != table[i][v]) {u = table[i][u];v = table[i][v];}}return table[0][u];}int climb(int u, int k) {if(dep[u] < k) return -1;for(int i = LOG - 1; i >= 0; i--) {if((k >> i) & 1) u = table[i][u];}return u;}int dist(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}int size(int u) {return sum[u];}private:void dfs(int idx, int par, int d) {table[0][idx] = par;dep[idx] = d;sum[idx] = 1;for(auto &to : g[idx]) {if(to != par) {sum[to] = sum[idx] + to.cost;dfs(to, idx, d + 1);sum[idx] += sum[to];}}}};int main() {int N, Q;cin >> N >> Q;DoublingLowestCommonAncestor< int > g(N);g.read(N - 1);g.build();while(Q--) {int a, b;cin >> a >> b;--a, --b;int d = g.dist(a, b);if(d % 2 == 1) {cout << 0 << endl;continue;}d /= 2;int lca = g.lca(a, b);if(g.dist(a, lca) == d) {cout << N - g.size(g.climb(a, d - 1)) - g.size(g.climb(b, d - 1)) << endl;} else {if(g.dist(a, lca) > g.dist(b, lca)) {swap(a, b);}cout << g.size(g.climb(b, d)) - g.size(g.climb(b, d - 1)) << endl;}}}