Hope you liked the problems!
include <bits/stdc++.h>
define all(x) (x).begin(), (x).end()
define allr(x) (x).rbegin(), (x).rend()
define gsize(x) (int)((x).size())
const char nl = '\n'; typedef long long ll; typedef long double ld;
using namespace std;
void solve() { int n; cin >> n;
vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; ll sum_a = 0, cnt_1 = 0; for (int x: a) { sum_a += x; if (x == 1) cnt_1++; } if (sum_a >= cnt_1 + n && n > 1) { cout << "YES" << nl; } else { cout << "NO" << nl; }
}
int main() { ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T; while (T--) { solve(); }
} ~~~~~
include <bits/stdc++.h>
define all(x) (x).begin(), (x).end()
define allr(x) (x).rbegin(), (x).rend()
define gsize(x) (int)((x).size())
const char nl = '\n'; typedef long long ll; typedef long double ld;
using namespace std;
void solve() { ll n, k; cin >> n >> k;
vector<ll> a(n); for (int i = 0; i < n; i++) cin >> a[i]; ll lb = 0, ub = *max_element(all(a)) + k, ans = 0; while (lb <= ub) { ll tm = (lb + ub) / 2; bool good = false; for (int i = 0; i < n; i++) { vector<ll> min_needed(n); min_needed[i] = tm; ll c_used = 0; for (int j = i; j < n; j++) { if (min_needed[j] <= a[j]) continue; if (j + 1 >= n) { c_used = k + 1; break; } c_used += min_needed[j] - a[j]; min_needed[j + 1] = max(min_needed[j + 1], min_needed[j] - 1); } if (c_used <= k) good = true; } if (good) { ans = tm; lb = tm + 1; } else { ub = tm - 1; } } cout << ans << nl;
}
int main() { ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) solve();
} ~~~~~
include <bits/stdc++.h>
define all(x) (x).begin(), (x).end()
define allr(x) (x).rbegin(), (x).rend()
define gsize(x) (int)((x).size())
const char nl = '\n'; typedef long long ll; typedef long double ld;
using namespace std;
int query(int l, int r) { if (l == r) return 0; cout << "? " << l << ' ' << r << endl;
int res; cin >> res; return res;
}
// Finds max on p[l; r] int solve(int l, int r) { if (l == r) return l;
int m = (l + r) / 2; int a = solve(l, m); int b = solve(m + 1, r); int r1, r2; r1 = query(a, b - 1); r2 = query(a, b); if (r1 == r2) { return b; } else { return a; }
}
void solve() { int n; cin >> n;
int ans = solve(1, n); cout << "! " << ans << endl;
}
int main() { ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T; while (T--) { solve(); }
} ~~~~~
1856E1 - PermuTree (easy version)
include <bits/stdc++.h>
define all(x) (x).begin(), (x).end()
define allr(x) (x).rbegin(), (x).rend()
define gsize(x) (int)((x).size())
const char nl = '\n'; typedef long long ll; typedef long double ld;
using namespace std;
const int maxn = 1000000;
vector g[maxn]; int s[maxn]; ll ans = 0;
void dfs(int v, int p = -1) { vector a; s[v] = 1;
for (int u: g[v]) { if (u == p) continue; dfs(u, v); s[v] += s[u]; a.push_back(s[u]); } vector<ll> dp(s[v]); ll cs = 0; for (int x: a) { for (ll i = cs + x; i >= 0; i--) { for (ll pr = min(cs, i); pr >= max(0LL, i - x); pr--) { ll j = i - pr; dp[i] = max(dp[i], dp[pr] + j * (cs - pr) + pr * (x - j)); } } cs += x; } ans += *max_element(all(dp)); dp.clear(); a.clear();
}
int main() { ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; for (int i = 1; i < n; i++) { int x; cin >> x; g[x - 1].push_back(i); } dfs(0); cout << ans << nl;
} ~~~~~
1856E2 - PermuTree (hard version)
include <bits/stdc++.h>
define all(x) (x).begin(), (x).end()
define allr(x) (x).rbegin(), (x).rend()
define gsize(x) (int)((x).size())
const char nl = '\n'; typedef long long ll; typedef long double ld;
using namespace std;
const int maxn = 1000000;
vector g[maxn]; int s[maxn]; ll ans = 0; vector b; ll closest;
template void subset_sum(int n) { if (n >= len) { subset_sum<std::min(len*2, maxn)>(n); return; }
bitset<len> dp; dp[0] = 1; for (ll x: b) { dp = dp | (dp << x); } ll cv = n; closest = 0; for (int i = 0; i <= n; i++) { if (dp[i] && abs(i - (n - i)) < cv) { closest = i; cv = abs(i - (n - i)); } }
}
ll solve(vector &a) { if (a.empty()) return 0;
sort(allr(a)); ll cs = 0; for (ll x: a) cs += x; if (a[0] * 2 >= cs) { return a[0]; } int n = gsize(a); a.push_back(0); b.clear(); int pi = 0; for (int i = 1; i <= n; i++) { if (a[i] != a[i - 1]) { ll cnt = i - pi; ll x = a[i - 1]; ll j = 1; while (j < cnt) { b.push_back(x * j); cnt -= j; j *= 2; } b.push_back(x * cnt); pi = i; } } subset_sum(cs); return closest;
}
void dfs(int v, int p = -1) { vector a; s[v] = 1;
for (int u: g[v]) { if (u == p) continue; dfs(u, v); s[v] += s[u]; a.push_back(s[u]); } ll x = solve(a); ans += x * (s[v] - 1 - x); a.clear();
}
int main() { ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; for (int i = 1; i < n; i++) { int x; cin >> x; g[x - 1].push_back(i); } dfs(0); cout << ans << nl;
} ~~~~~