2236A - Games on the Train
Идея: arsen1y
Решение (arsen1y)#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = (int) 1e18;
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int _;
cin >> _;
while (_--) {
int n;
cin >> n;
vector <int> a(n);
int mx = -INF;
int mn = INF;
for (int i = 0; i < n; ++i) {
cin >> a[i];
mx = max(mx, a[i]);
mn = min(mn, a[i]);
}
cout << mx - mn + 1 << "\n";
}
return 0;
}
2236B - Tatar TV Show
Идея: eyfxrby
ПодсказкаПопробуйте найти свойство, которое не изменяется при проведении операций.
Решение (eyfxrby)#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k; cin >> n >> k;
string s; cin >> s;
vector<int> cnt(k, 0);
for (int i = 0; i < n; i++) cnt[i % k] += s[i] - '0';
bool ok = true;
for (int r = 0; r < k; r++) {
if (cnt[r] % 2) {
ok = false;
break;
}
}
cout << (ok ? "YES" : "NO") << '\n';
}
}
2236C - Omsk Programmers
Идея: arsen1y
ПодсказкаМожно показать, что выгодно сначала делать только деления, а потом только прибавления.
Решение (arsen1y)#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = (int) 1e18;
int32_t main() {
int _;
cin >> _;
while (_--) {
int a, b, x;
cin >> a >> b >> x;
int ans = INF;
int i = 0;
while (a != b) {
if (b > a) {
swap(a, b);
}
ans = min(ans, abs(a - b) + i);
a /= x;
i++;
}
ans = min(ans, i);
cout << ans << "\n";
}
return 0;
}
2236D - Brand New Tatar TV Show
Идея: dvb1r
Подсказка 1Что произойдёт, если Арсений первым ходом выберет максимум массива?
ОтветЕсли количество максимумов нечетное, то выиграет Дабир, иначе Егор.
Подсказка 2Попробуйте посмотреть на второй максимум
Решение (dvb1r)#include <bits/stdc++.h>
using namespace std;
void solve();
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
void solve() {
int n, k; cin >> n >> k;
vector<int> A(n);
for (auto& x : A) cin >> x;
sort(A.begin(), A.end());
vector<pair<int, int>> a = {{A[0], 1}};
for (int i = 1; i < n; ++i) {
if (A[i] == A[i - 1]) a.back().second++;
else a.emplace_back(A[i], 1);
}
while (a.size() > 0) {
n = a.size();
if (a[n - 1].second % 2 == 0) {
cout << "YES\n";
return;
}
if (n == 1) {
cout << "NO\n";
return;
}
if (a[n - 1].first - a[n - 2].first <= k) {
cout << "YES\n";
return;
}
a.pop_back();
}
}
2236E - Friendly Gifts
Идея: arsen1y
ПодсказкаОтрезки массива не нужно проверять на непересечение.
Решение (dvb1r)#include <bits/stdc++.h>
using namespace std;
void solve();
int main() {
int t = 1; cin >> t;
while (t--) solve();
return 0;
}
void solve() {
int n; cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x, --x;
vector<vector<bool>> able(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
vector<int> us(n);
int mn = a[i], mx = a[i];
for (int j = i; j < n; ++j) {
if (us[a[j]]) break;
us[a[j]] = 1;
mn = min(mn, a[j]), mx = max(mx, a[j]);
if (mx - mn == j - i) able[mn][mx] = 1;
}
}
for (int ans = n; ans > 0; --ans) {
for (int i = 0; i + 2 * ans <= n; ++i) {
if (able[i][i + ans - 1] && able[i + ans][i + 2 * ans - 1]) {
cout << ans << '\n';
return;
}
}
}
cout << "0\n";
}
2236F1 - Elections in Saransk (easy version)
Идея: eyfxrby
Подсказка 1Что можно сказать про $$$gcd(p_i, p_j)$$$ для любой пары $$$(i, j)$$$?
Подсказка 2Возьмем какое то простое число $$$pr$$$. Сколько элементов массива p может быть кратно этому $$$pr$$$?
Решение (eyfrxby)#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace __gnu_pbds;
using namespace std;
#define eps 1e-7
#define MOD2 119 * (1ll << 23) + 1
#define int long long
#define mp make_pair
#define pll pair <long long, long long>
#define next return
#define skip continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define f first
#define max_of max_element
#define min_of min_element
#define s second
// const int MAX_MEM = 4e8;
// int mpos = 0;
// alignas(long long) char mem[MAX_MEM];
// inline void * operator new(size_t n) {
// if (n & 7) n += 8 - (n & 7);
// char *res = mem + mpos;
// mpos += n;
// return (void *)res;
// }
// void operator delete(void *) {}
int scan() {
int x;
cin >> x;
return x;
}
string read() {
string s;
cin >> s;
return s;
}
const int N = 1e6 + 5, MOD = 1e9 + 7;
int lp[N], a[N], x, n, v[101];
vector<int> pr, divs[N];
int bin_pow(int x, int n) {
int res = 1;
while (n) {
if ((n & 1)) res = res * x % MOD;
n >>= 1;
x = x * x % MOD;
}
return res;
}
int solveF1_AUTHOR() {
map <int, int> cnt;
int cur_x;
int mx = *max_element(a + 1, a + n + 1);
set <int> setik;
for (int i = 1; i <= n; i++) {
int val = a[i];
cur_x = val;
while (cur_x > 1) {
setik.insert(lp[cur_x]);
cnt[lp[cur_x]]++;
cur_x /= lp[cur_x];
}
}
int ans = 1;
for (auto prime: setik) {
int sum = 1;
//cout << prime << ' ' << cnt[prime] << '\n';
ans = (ans * (cnt[prime] + 1)) % MOD;
}
return ans;
}
int32_t main() {
lp[1] = 1;
for (int i = 2; i < N; i++) {
if (lp[i] == 0) {
pr.push_back(i);
lp[i] = i;
}
for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
lp[i * pr[j]] = pr[j];
}
}
int t = scan();
while (t--) {
n = scan(); x = scan();
for (int i = 1; i <= n; i++) a[i] = scan();
cout << solveF1_AUTHOR() << '\n';
}
}
2236F2 - Elections in Saransk (hard version)
Идея: eyfxrby
Решение 1 (eyfrxby)#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace __gnu_pbds;
using namespace std;
#define eps 1e-7
#define MOD2 119 * (1ll << 23) + 1
#define int long long
#define mp make_pair
#define pll pair <long long, long long>
#define next return
#define skip continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define f first
#define max_of max_element
#define min_of min_element
#define s second
int scan() {
int x;
cin >> x;
return x;
}
string read() {
string s;
cin >> s;
return s;
}
const int N = 1e6 + 2, MOD = 1e9 + 7;
int lp[N], a[N], x, n, v[N];
vector<int> pr, divs[N];
int MAX_V = -1E9;
int solve_for_prime(int vp) {
int mx_pref = 0;
int S = 0;
for (int i = 1; i <= n; i++) S += v[i];
S = min(S, 36ll);
int dp[MAX_V + 1][MAX_V + S + 2];
int old_pref_sum[MAX_V + 1][MAX_V + S + 2];
int old_pref_sum2[MAX_V + 1][MAX_V + S + 2];
memset(dp, 0, sizeof dp);
memset(old_pref_sum, 0, sizeof old_pref_sum);
memset(old_pref_sum2, 0, sizeof old_pref_sum2);
int sum = 0;
dp[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int sum_vp = 0; sum_vp <= S && i > 0; sum_vp++) {
for (int new_max = 1; new_max <= min(sum_vp, v[i]); new_max++) {
dp[new_max][sum_vp] += old_pref_sum2[new_max - 1][sum_vp - new_max];
if (dp[new_max][sum_vp] >= MOD) dp[new_max][sum_vp] -= MOD;
}
for (int old_max = 0; old_max <= min(mx_pref, sum_vp); old_max++) {
dp[old_max][sum_vp] += (old_pref_sum[old_max][sum_vp] + MOD - (sum_vp - min(old_max, v[i]) - 1 < 0 ? 0 :
old_pref_sum[old_max][sum_vp - min(old_max, v[i]) - 1])) % MOD;
//if (dp[old_max][sum_vp] >= MOD) dp[old_max][sum_vp] -= MOD;
}
}
for (int old_max = 0; old_max <= MAX_V; old_max++) {
for (int j = 0; j <= MAX_V + S; j++) {
old_pref_sum[old_max][j] = 0;
old_pref_sum[old_max][j] = (!j ? dp[old_max][j] : old_pref_sum[old_max][j - 1] + dp[old_max][j]);
if (old_pref_sum[old_max][j] >= MOD) old_pref_sum[old_max][j] -= MOD;
}
}
for (int j = 0; j <= MAX_V + S; j++) {
for (int old_max = 0; old_max <= MAX_V; old_max++) {
old_pref_sum2[old_max][j] = 0;
old_pref_sum2[old_max][j] = (!old_max ? dp[old_max][j] : old_pref_sum2[old_max - 1][j] + dp[old_max][j]);
if (old_pref_sum2[old_max][j] >= MOD) old_pref_sum2[old_max][j] -= MOD;
if(i != n) dp[old_max][j] = 0;
}
}
mx_pref = max(mx_pref, v[i]);
}
int ret = 0;
for (int mx = 1; vp + mx <= S && mx <= MAX_V; mx++) {
ret = (ret + dp[mx][vp + mx]);
if (ret >= MOD) ret -= MOD;
}
return ret;
}
int solveF2_AUTHOR() {
map<int, int> cnt_pr;
int cur_x = x;
while (cur_x > 1) {
int next_div = lp[cur_x];
cnt_pr[next_div]++;
cur_x /= next_div;
}
int ans = 1;
for (auto [prime, cnt]: cnt_pr) {
MAX_V = -1e9;
for (int i = 1; i <= n; i++) {
cur_x = a[i];
v[i] = 0;
while (cur_x % prime == 0) {
v[i]++;
cur_x /= prime;
}
MAX_V = max(MAX_V, v[i]);
}
ans = (ans * solve_for_prime(cnt)) % MOD;
}
map <int, int> cnt;
int mx = *max_element(a + 1, a + n + 1);
set <int> setik;
for (int i = 1; i <= n; i++) {
int val = a[i];
cur_x = val;
while (cur_x > 1) {
cnt[lp[cur_x]]++;
setik.insert(lp[cur_x]);
cur_x /= lp[cur_x];
}
}
for (auto prime: setik) {
//if (2 * prime > mx) break;
int sum = 1;
if (x % prime != 0) ans = (ans * (cnt[prime] + 1)) % MOD;
}
return ans;
}
int32_t main() {
for (int i = 2; i < N; i++) {
if (lp[i] == 0) {
pr.push_back(i);
lp[i] = i;
}
for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {
lp[i * pr[j]] = pr[j];
}
}
int t = scan();
while (t--) {
n = scan(), x = scan();
for (int i = 1; i <= n; i++) a[i] = scan();
cout << solveF2_AUTHOR() << '\n';
}
}
Решение 2 (Treks)//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <experimental/random>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using str = string;
const ll INF = 1e18, MOD = 1e9 + 7;
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
#define int long long
void solve();
vector<int> P;
const int Mx = 1e4;
signed main() {
vector<bool> us(Mx);
for (int i = 2; i < Mx; ++i) {
if (!us[i]) {
P.push_back(i);
for (int j = i * i; j < Mx; j += i) {
us[j] = true;
}
}
}
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll q = 1;
cin >> q;
while (q--) {
solve();
cout << "\n";
}
}
void solve() {
int n, x;
cin >> n >> x;
map<int, int> cnt;
for (auto w: P) {
if (w * w > x) {
break;
}
while (x % w == 0) {
x /= w;
cnt[w]++;
}
}
if (x > 1) {
cnt[x]++;
}
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
map<int, vector<int>> w1;
for (int i = 0; i < n; ++i) {
for (auto w: P) {
if (w * w > a[i]) {
break;
}
int sum = 0;
while (a[i] % w == 0) {
a[i] /= w;
sum++;
}
if (sum > 0) {
w1[w].push_back(sum);
}
}
if (a[i] > 1) {
w1[a[i]].push_back(1);
}
}
int Ans = 1;
for (auto [id, e]: w1) {
int mx = 0;
for (auto s: e) {
mx = max(mx, s);
}
vector<vector<int>> dp(cnt[id] + 1, vector<int>(mx + 1));
dp[0][0] = 1;
for (auto w: e) {
vector<vector<int>> dp1(cnt[id] + 1, vector<int>(mx + 1));
for (int i = 0; i <= w; ++i) {
for (int j = 0; j <= cnt[id]; ++j) {
for (int k = 0; k <= mx; ++k) {
if (j + min(i, k) <= cnt[id]) {
dp1[j + min(i, k)][max(i, k)] += dp[j][k];
dp1[j + min(i, k)][max(i, k)] %= MOD;
}
}
}
}
swap(dp, dp1);
}
int s = 0;
for (int i = 0; i <= mx; ++i) {
s += dp[cnt[id]][i];
}
s %= MOD;
Ans *= s;
Ans %= MOD;
cnt[id] = 0;
}
for (auto s: cnt) {
if (s.second > 0) {
Ans = 0;
}
}
cout << Ans;
}
2236G - Criterion in Burlandia
Идея: dvb1r
Подсказка 1На самом деле XOR неотрицательных чисел всегда $$$\leq$$$ их суммы, можете подумать почему.
Подсказка 2Используя факт, что XOR множества чисел равен сумме этих чисел, сколько в этом множестве может быть ненулевых чисел?
ОтветНе более $$$log(A)$$$, так как каждый бит должен встречаться не более одного раза.
Подсказка 3Для каждой вершины предподсчитайте ближайшего предка, на вертикальном пути до которого нарушается условие хорошего отрезка.
Подсказка 4Сведите к задачу к пути длиной не более $$$2 * log(A)$$$, а остальное посчитайте используя предподсчет из подсказки 3.
Решение 1 (dvb1r)#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve();
int main() {
int t = 1;
cin >> t;
while (t --> 0) solve();
return 0;
}
struct Graph {
vector<int> tin, tout, d;
vector<vector<pair<int, ll>>> up;
int timer;
void dfs(int v, const vector<vector<int>>& g, const vector<int>& arr, int p = -1) {
tin[v] = timer++;
up[0][v] = {p, arr[v]};
for (int l = 1; l < 20; ++l) {
if (up[l - 1][v].first == -1) {
up[l][v] = {-1, 0};
continue;
}
up[l][v].first = up[l - 1][up[l - 1][v].first].first;
up[l][v].second = up[l - 1][up[l - 1][v].first].second + up[l - 1][v].second;
}
for (int u : g[v]) {
if (u == p) continue;
d[u] = d[v] + 1;
dfs(u, g, arr, v);
}
tout[v] = timer;
}
Graph(const vector<vector<int>>& g, const vector<int>& a) : tin(g.size()), tout(g.size()), d(g.size()), up(20, vector<pair<int, ll>>(g.size())) {
timer = 0;
dfs(0, g, a);
}
bool anc(int p, int v) {
return tin[p] <= tin[v] && tout[p] >= tout[v];
}
int getLenVertical(int u, int v) {
if (!anc(u, v)) swap(u, v);
assert(anc(u, v));
return d[v] - d[u] - 1;
}
pair<int, ll> LA(int v, int k) {
if (k <= 0) return {v, 0};
ll sum = 0;
for (int i = 0; i < 20; ++i) {
if (k >> i & 1) sum += up[i][v].second, v = up[i][v].first;
}
return {v, sum};
}
int LCA(int u, int v) {
if (anc(u, v)) return u;
for (int l = 19; l >= 0; --l) {
if (up[l][u].first == -1 || anc(up[l][u].first, v)) continue;
u = up[l][u].first;
}
return up[0][u].first;
}
bool lower(int a, int b) {
return tin[a] < tin[b];
}
};
ll sum(int r) { return r * 1ll * (r + 1) / 2; }
ll sumSeg(int l, int r) {
return sum(r) - sum(l - 1);
}
void solve() {
int n, q; cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<vector<int>> g(n);
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
--u, --v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vector<int> parent(n), d(n);
auto dfs = [&](auto& self, int v, int p = -1) -> void {
parent[v] = p;
for (int u : g[v]) {
if (u == p) continue;
d[u] = d[v] + 1;
self(self, u, v);
}
};
dfs(dfs, 0);
vector<int> compressed_parent = parent;
vector<vector<int>> cG(n);
for (int v = 0; v < n; ++v) {
vector<int> path;
while (compressed_parent[v] > 0 && a[compressed_parent[v]] == 0) {
path.emplace_back(compressed_parent[v]);
compressed_parent[v] = compressed_parent[compressed_parent[v]];
}
for (auto& x : path) compressed_parent[x] = compressed_parent[v];
if (a[v] == 0 || !v) continue;
cG[compressed_parent[v]].emplace_back(v);
}
vector<int> next_collision(n), sum_collision(n);
for (int v = 0; v < n; ++v) {
if (!a[v]) continue;
next_collision[v] = v;
int xr = a[v], sm = a[v];
while (xr == sm && next_collision[v] > -1) {
next_collision[v] = compressed_parent[next_collision[v]];
if (next_collision[v] == -1) break;
xr ^= a[next_collision[v]];
sm += a[next_collision[v]];
}
}
for (int v = 0; v < n; ++v) {
if (!a[v]) {
if (!v) next_collision[v] = -1;
else next_collision[v] = next_collision[compressed_parent[v]];
}
sum_collision[v] = d[v];
if (next_collision[v] > -1) sum_collision[v] -= d[next_collision[v]];
else sum_collision[v]++;
}
Graph def(g, sum_collision);
Graph compressed(cG, sum_collision);
while (q--) {
int u, v; cin >> u >> v;
--u, --v;
if (def.lower(v, u)) swap(u, v);
int z = def.LCA(u, v);
int cv = (a[v] || !v ? v : compressed_parent[v]), cu = (a[u] || !u ? u : compressed_parent[u]), cz = (a[z] || !z ? z : compressed_parent[z]);
ll ans = 0;
vector<int> L, R, Lspaces = {0}, Rspaces = {0};
if (compressed.d[cv] > compressed.d[cz] + 23) {
int unt = compressed.LA(cv, compressed.d[cv] - (compressed.d[cz] + 23)).first;
auto [to, sm] = def.LA(v, d[v] - d[unt]);
ans += sm, v = to;
}
if (compressed.d[cu] > compressed.d[cz] + 23) {
int unt = compressed.LA(cu, compressed.d[cu] - (compressed.d[cz] + 23)).first;
auto [to, sm] = def.LA(u, d[u] - d[unt]);
ans += sm, u = to;
}
while (u != z) {
int to = compressed_parent[u];
if (def.anc(to, z)) to = z;
L.emplace_back(u);
Lspaces.emplace_back(def.getLenVertical(u, to));
u = to;
}
while (v != z) {
int to = compressed_parent[v];
if (def.anc(to, z)) to = z;
R.emplace_back(v);
Rspaces.emplace_back(def.getLenVertical(v, to));
v = to;
}
L.emplace_back(z);
std::reverse(R.begin(), R.end());
std::reverse(Rspaces.begin(), Rspaces.end());
for (auto& x : R) L.emplace_back(x);
for (auto& x : Rspaces) Lspaces.emplace_back(x);
int j = 0, xr = 0, sum = 0;
ll cnt = 0;
for (int i = 0; i < L.size(); ++i) {
while (j < L.size() && xr == sum) {
xr ^= a[L[j]], sum += a[L[j]];
cnt += Lspaces[j] + 1;
j++;
}
if (xr != sum) cnt--;
ans += sumSeg(cnt - Lspaces[i], cnt);
if (xr != sum) cnt++;
xr ^= a[L[i]], sum -= a[L[i]];
cnt -= Lspaces[i] + 1;
}
cout << ans << '\n';
}
}
<spoiler summary="Решение 2 (Treks)" ~~~~~ //#pragma GCC optimize("Ofast") //#pragma GCC optimize("O3,unroll-loops")
include <bits/stdc++.h>
include <experimental/random>
include <ext/pb_ds/assoc_container.hpp>
using namespace std; using namespace __gnu_pbds;
using ll = long long; using ld = long double; using ordered_set = tree<ll, null_type, less, rb_tree_tag, tree_order_statistics_node_update>; using str = string; const ll INF = 1e18, MOD = 1e9 + 7; template using pq_min = priority_queue<T, vector, greater>; template using pq_max = priority_queue<T, vector, less>;
define int long long
void solve();
signed main() {
ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll q = 1;
cin >> q;
while (q--) {
solve();
//cout << "\n";
}}
vector<vector> g; vector a; int h; vector us; int cnt1; vector T;
void dfs1(int v, int pr) { T.push_back(v); cnt1++; for (auto to: g[v]) { if (to != pr && !us[to]) { dfs1(to, v); } } }
int dfs(int v, int pr) { bool p = true; int cnt = 1; for (auto to: g[v]) { if (to != pr && !us[to]) { auto u = dfs(to, v); if (u > cnt1 / 2) { p = false; } cnt += u; } } if (p && (cnt1 — cnt) <= cnt1 / 2) { h = v; } return cnt; }
int E = 0;
vector ans; vector<vector> mn; vector col; vector sz; vector W;
void dfs(int v, int pr, vector s, int an, int o, int mx) { sz[v] = o; col[v] = E; W[v] = W[pr]; for (int i = 0; i < 20; ++i) {
mn[v][i] = mn[pr][i]; } for (int i = 0; i < 20; ++i) { if ((a[v] >> i) & 1) { if (mn[v][i] != INF) { W[v] = min(W[v], o); } mn[v][i] = min(mn[v][i], o); mx = max(mx, s[i]); s[i] = o; } } an += o — mx; ans[v] = an; for (auto to: g[v]) { if (to != pr && !us[to]) { dfs(to, v, s, an, o + 1, mx); } } }
vector<vector<pair<int, int>>> que; vector ANS;
void rec(int v) { T.clear(); cnt1 = 0; dfs1(v, -1); dfs(v, -1); v = h; us[v] = true; mn[v] = vector(20, INF); int S = E; W[v] = INF; for (auto to: g[v]) { if (!us[to]) { E++; vector s(20, 0); dfs(to, v, s, 0, 1, 0); } } ans[v] = 0; ++E; col[v] = E; for (auto x: T) { for (auto [y, id]: que[x]) { if (col[x] != col[y] && col[x] > S && col[y] > S) { ANS[id] = ans[x] + ans[y]; if (x == v) { int MN = min(W[y], sz[y] + 1); for (int i = 0; i < 20; ++i) { if ((a[v] >> i) & 1) { MN = min(MN, mn[y][i]); } } ANS[id] += MN; } else if (y == v) { int MN = min(W[x], sz[x] + 1); for (int i = 0; i < 20; ++i) { if ((a[v] >> i) & 1) { MN = min(MN, mn[x][i]); } } ANS[id] += MN; } else { vector<pair<int, int>> upd; for (int i = 0; i < 20; ++i) { if (mn[x][i] != INF) { upd.push_back({mn[x][i], i}); } } int e = min(W[y], sz[y] + 1); for (int i = 0; i < 20; ++i) { if ((a[v] >> i) & 1) { e = min(e, mn[y][i]); } } sort(upd.begin(), upd.end()); int p = 0; bool flag = true; for (int i = 0; i < upd.size(); ++i) { if (upd[i].first >= W[x]) { ANS[id] += (W[x] — p) * e; flag = false; break; } ANS[id] += (upd[i].first — p) * e; if ((a[v] >> upd[i].second) & 1) { flag = false; break; } e = min(e, mn[y][upd[i].second]); p = upd[i].first; } if (flag) { ANS[id] += (min(W[x], sz[x] + 1) — p) * e; } } } } } for (int i = 0; i < g[v].size(); ++i) { int to = g[v][i]; if (!us[to]) { rec(to); } } }
void solve() { int n, q; cin >> n >> q; sz.clear(); W.clear(); W.resize(n); sz.resize(n); ans.clear(); ANS.clear(); ANS.resize(q, -1); mn.clear(); ans.resize(n); mn.resize(n, vector(20)); a.clear(); us.clear(); us.resize(n); a.resize(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } g.clear(); col.clear(); col.resize(n); que.clear(); que.resize(n); g.resize(n); for (int i = 0; i < n — 1; ++i) { int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); g[v].push_back(u); } for (int i = 0; i < q; ++i) { int x, y; cin >> x >> y; --x; --y; que[x].push_back({y, i}); } rec(0); for (int i = 0; i < q; ++i) { if (ANS[i] == -1) { exit(-1); } cout << ANS[i] << "\n"; } } ~~~~~
