結果
| 問題 |
No.2337 Equidistant
|
| コンテスト | |
| ユーザー |
 Alex Wice
|
| 提出日時 | 2023-06-02 22:36:15 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,691 bytes |
| コンパイル時間 | 5,370 ms |
| コンパイル使用メモリ | 282,852 KB |
| 実行使用メモリ | 74,268 KB |
| 最終ジャッジ日時 | 2024-12-28 20:19:09 |
| 合計ジャッジ時間 | 15,942 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 1 WA * 27 |
ソースコード
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// clang-format off
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using str = string;
using AR2 = array<int, 2>;
template <class T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vec<vec<T>>;
template <class T> using vvvec = vec<vvec<T>>;
template <class T, size_t SZ> using vac = vec<array<T, SZ>>;
template <class T, size_t SZ> using vvac = vec<vac<T, SZ>>;
// template <class T> using priority_queue_min = priority_queue<T, vec<T>, greater<T>>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define pb push_back
#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(int)(b):i>(int)(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define E_ACH2(x, a) for (auto& x: a)
#define E_ACH3(x, y, a) for (auto& [x, y]: a)
#define E_ACH4(x, y, z, a) for (auto& [x, y, z]: a)
#define E_ACHC(...) GET5(__VA_ARGS__, E_ACH4, E_ACH3, E_ACH2)
#define EACH(...) E_ACHC(__VA_ARGS__)(__VA_ARGS__)
#define SUBMASKS(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
constexpr int popcount(int x) { return __builtin_popcount(x); }
constexpr int bitlength(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
ll cdiv(ll a, ll b) { return a/b + ((a^b) > 0 && a % b); };
ll fdiv(ll a, ll b) { return a/b - ((a^b) < 0 && a % b); };
template <class T> T pop(vec<T> &v) { T x = v.back(); v.pop_back(); return x; }
template <class T> bool bounds(T a, T lo, T hi) { return lo <= a && a <= hi; }
template <class T> T truemod(T x, T M) { return (x % M + M) % M; }
template <class T> bool umin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <class T> bool umax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template <class T> int lwb(vec<T> &a, T &b) { return int(lower_bound(all(a), b) - begin(a)); }
template <class T> int upb(vec<T> &a, T &b) { return int(upper_bound(all(a), b) - begin(a)); }
template <class T> void removeDupes(vec<T> &v) { sort(all(v)); v.erase(unique(all(v)), end(v)); }
template <class T, class U> void eraseOne(T &t, U &u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }
template <class T, class U> T firstTrue(T lo, T hi, U f) {
++hi; assert(lo <= hi);
while (lo < hi) {
T mi = lo + (hi-lo) / 2;
f(mi) ? hi = mi : lo = mi + 1;
}
return lo;
}
template <class T, class U> T lastTrue(T lo, T hi, U f) {
--lo; assert(lo <= hi);
while (lo < hi) {
T mi = lo + (hi-lo+1) / 2;
f(mi) ? lo = mi : hi = mi - 1;
}
return lo;
}
template <class T, size_t SZ> istream &operator>>(istream &s, array<T, SZ>& v) { FOR(sz(v)) s >> v[i]; return s; }
template <class T> istream &operator>>(istream &s, vec<T>& v) { FOR(sz(v)) s >> v[i]; return s; }
template <class T> ostream &operator<<(ostream &s, vec<T>& v) { FOR(sz(v)) s << (i?" ":"") << v[i]; return s; }
template <class T> ostream &operator<<(ostream &s, const vec<T>& v) { FOR(sz(v)) s << (i?" ":"") << v[i]; return s; }
template<class A> void write(A x) { cout << x; }
template<class H, class... T> void write(const H& h, const T&... t) {
write(h); write(t...); }
void print() { write("\n"); }
template<class H, class... T> void print(const H& h, const T&... t) {
write(h); if (sizeof...(t)) write(" "); print(t...); }
void decrement() {}
template <class T, size_t SZ> void decrement(vec<array<T, SZ>> &v) { EACH(row, v) EACH(x, row) --x; }
template <class T> void decrement(vec<vec<T>> &v) { EACH(row, v) EACH(x, row) --x; }
template <class T> void decrement(vec<T> &v) { EACH(x, v) --x; }
template <class T, class... U> void decrement(T &t, U &...u) { --t; decrement(u...); }
template <class T> void read(T& x) { cin >> x; }
template<class T, class... U> void read(T &t, U &...u) { read(t); read(u...); }
#define ints(...) int __VA_ARGS__; read(__VA_ARGS__);
#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
#define vint(n, a) int n; cin >> n; vec<int> a(n); cin >> a;
#define vin(n, a) vec<int> a((n)); cin >> a;
#define vvin(n, m, a) vec<vec<int>> a((n), vec<int>((m))); cin >> a;
#define vain(n, m, a) vec<array<int, (m)>> a((n)); cin >> a;
#define graphin(n, m, adj) vvec<int> adj(n); FOR(m) {int1(u, v); adj[u].pb(v); adj[v].pb(u); }
#define lgraphin(n, m, adj) vvac<int, 2> adj(n); FOR(i, m) {int1(u, v); adj[u].pb({v,i}); adj[v].pb({u,i}); }
#define wgraphin(n, m, adj) vvac<int, 2> adj(n); FOR(m) {int1(u, v); ints(w); adj[u].pb({v,w}); adj[v].pb({u,w}); }
#define dgraphin(n, m, adj) vvec<int> adj(n); FOR(m) {int1(u, v); adj[u].pb(v);}
#define dwgraphin(n, m, adj) vvac<int, 2> adj(n); FOR(m) {int1(u, v, w); adj[u].pb({v, w+1});}
// clang-format on
struct ancestor {
vector<int> vin, vout, d;
vector<vector<int>> adj, p;
vector<int> size;
int n, t = 0, e;
void dfs(int i, int v) {
vin[i] = t++;
p[i][0] = v, d[i] = d[v] + 1;
for (int j = 1; j <= e; j++)
p[i][j] = p[p[i][j - 1]][j - 1];
for (auto& j : adj[i])
if (j != v) {
dfs(j, i);
size[i] += size[j];
}
vout[i] = t - 1;
}
// accepts an adjecency list. can include or exlude parents, it works either way.
// constructor runs in O(nlogn) time.
ancestor(vector<vector<int>> _adj = {}, int root = 0)
: adj(_adj)
, n(_adj.size()) {
if (adj.empty())
return;
vin.resize(n), vout.resize(n), d.assign(n, 0);
size.assign(n, 1);
e = ceil(log2(n));
p.assign(n, vector<int>(e + 1));
dfs(root, root);
}
// returns true if i is an ancestor of j in O(1) time.
bool is_ancestor(int i, int j) const {
return vin[i] <= vin[j] && vout[i] >= vout[j];
}
// returns the k'th ancestor of i O(logk) time.
int ktha(int i, int k) const {
while (k) {
int j = k & -k;
i = p[i][__builtin_ctz(j)];
k -= j;
}
return i;
}
// returns the LCA of i and j in O(logn) time.
int lca(int i, int j) const {
if (is_ancestor(i, j))
return i;
if (is_ancestor(j, i))
return j;
for (int k = e; k >= 0; k--)
if (!is_ancestor(p[i][k], j))
i = p[i][k];
return p[i][0];
}
// returns the vertex one step along the path from i to j in O(logn) time.
int step(int i, int j) const {
return is_ancestor(i, j) ? ktha(j, d[j] - d[i] - 1) : p[i][0];
}
// returns the vertex k steps along the path from i to j in O(logn) time.
int step(int i, int j, int k) const {
int l = lca(i, j);
return d[i] - d[l] >= k ? ktha(i, k) : ktha(j, d[i] + d[j] - 2 * d[l] - k);
}
// returns the number of edges between i and j in O(logn) time.
int dist(int i, int j) {
return d[i] + d[j] - 2 * d[lca(i, j)];
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ints(N, Q);
graphin(N, N - 1, adj);
vac<int, 2> queries(Q);
cin >> queries;
decrement(queries);
ancestor anc(adj);
EACH(s, t, queries) {
int lca = anc.lca(s, t);
int d1 = anc.d[s], d2 = anc.d[t];
int dlca = anc.d[lca];
int d = d1 + d2 - 2 * dlca;
if (d % 2) {
print(0);
continue;
}
d >>= 1;
int cand = 0;
if (d1 == d2) {
// debug(d1, d2, dlca);
cand += N;
// cand -= anc.size[lca];
// cand -= 1;
int lca_s = anc.ktha(s, d1 - dlca - 1);
cand -= anc.size[lca_s];
lca_s = anc.ktha(t, d2 - dlca - 1);
cand -= anc.size[lca_s];
print(cand);
continue;
}
if (d1 < d2) {
swap(d1, d2);
swap(s, t);
}
int pivot = anc.ktha(s, d);
cand = anc.size[pivot];
cand -= 1;
int lca_s = anc.ktha(s, d1 - anc.d[pivot] - 1);
cand -= anc.size[lca_s];
print(cand);
}
return 0;
}