Codeforces Round 862 (Div. 2)

先简单写一下 A-E 的题解。

A

异或的经典性质：$x\oplus x=0$。

B

显然要把字典序最小的那个字母放到最前面。

如果这个字母出现了很多次，那么应该选择最后一次出现的位置。这也很容易证明。

C

联立以后计算一下就行了。

比赛的时候爆了一次 int。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 2e5 + 5;
const ll mod = 998244353;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };
const double eps = 1e-6;void solve() {int n, m;cin >> n >> m;vector<int> K(n);for (int i = 0; i < n; ++i) {cin >> K[i];}vector<tuple<ll, ll, ll>> parabolas(m);for (int i = 0, a, b, c; i < m; ++i) {cin >> a >> b >> c;parabolas[i] = {a, b, c};}sort(K.begin(), K.end());for (auto [A, B, C] : parabolas) {if (C <= 0) {cout << "NO" << endl;} else {ll sAC = sqrt(4.0 * A * C);if (sAC * sAC == A * C * 4) sAC--;auto it = lower_bound(K.begin(), K.end(), B - sAC);if (it == K.end()) { cout << "NO" << endl;} else if (*it > B + sAC) {cout << "NO" << endl;} else {cout << "YES\\n" << (*it) << endl;}}}cout << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) {solve();}
}

D

容易发现，当 $k$ 从大到小变化时，点会一层一层的加进连通块里。

然后这个 $k$ 的最大值是树的直径，所以点的层数应该以直径为标准进行统计。

最后模拟这个加点的过程即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };vector<int> g[maxn];
int dep[maxn], h[maxn];
int mxdep, root;
void dfs0(int u, int f) {dep[u] = dep[f] + 1;for (auto v : g[u]) {if (v == f) continue;dfs0(v, u);}if (dep[u] >= mxdep) {mxdep = dep[u];root = u;}
}
void dfs(int u, int f) {dep[u] = dep[f] + 1;for (auto v : g[u]) {if (v == f) continue;dfs(v, u);}h[u] = max(h[u], dep[u]);
}
void solve() {int n;cin >> n;for (int i = 1, u, v; i < n; ++i) {cin >> u >> v;g[u].pb(v), g[v].pb(u);}dep[0] = -1;mxdep = 0;dfs0(1, 0);int r = root;dfs0(root, 0);dfs(r, 0);dfs(root, 0);vector<int> cnt(n + 5, 0);for (int i = 1; i <= n; ++i) {cnt[h[i]]++;}cnt[mxdep]--;vector<int> ans(n + 5, n);for (int k = mxdep; k >= 1; --k) {ans[k] = ans[k + 1] - cnt[k];}for (int i = 1; i <= n; ++i) {cout << ans[i] << " \\n"[i == n];}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;// cin >> T;while (T--) {solve();}
}

E

比赛的时候时间不够了，想写个 dsu on tree 试一下，可惜最后还是没写完。

这题的正解其实很简单，考虑整棵树的 MAD，如果这个数出现的次数不是 $2$，那么不管断哪条边都不会改变答案。如果出现次数正好是 $2$，那么只有这两个点之间的链被断开的时候，答案才会变化。所以先把链提取出来，然后在链上面按顺序算过去就行了。

如果没有观察到这个性质，用 dsu on tree 其实也是能做的。但是会跑的慢一些。

不加任何优化的 dsu on tree 几乎是贴着时限过的。最好还是优化一下，比如先离散化一下，省掉两个 map，就可以跑的和正解一样快了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define endl '\\n'
using ll = long long;
using pii = pair<int, int>;
const int maxn = 1e5 + 5;
const ll mod = 998244353;
const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, -1, 0, 1 };vector<pii> g[maxn];
int w[maxn];
map<int, int> subtree, total;
set<int> smad, tmad;
int sz[maxn], big[maxn];
int L[maxn], R[maxn], dfn, node[maxn];
int ans[maxn], edge_id[maxn];
void dfs0(int u, int f) {L[u] = ++dfn;node[dfn] = u;sz[u] = 1;for (auto [v, e] : g[u]) {if (v == f) continue;edge_id[v] = e;dfs0(v, u);sz[u] += sz[v];if (!big[u] || sz[big[u]] < sz[v])big[u] = v;}R[u] = dfn;
}
void add(int x) {subtree[x]++;if (subtree[x] == 2)smad.insert(x);total[x]--;if (total[x] == 1)tmad.erase(x);
}
void del(int x) {total[x]++;if (total[x] == 2)tmad.insert(x);subtree[x]--;if (subtree[x] == 1)smad.erase(x);
}
int MAD() {int mx = 0;if (!smad.empty()) {mx = max(mx, *smad.rbegin());}if (!tmad.empty()) {mx = max(mx, *tmad.rbegin());}return mx;
}
void dfs1(int u, int f, bool keep) {for (auto [v, e] : g[u]) {if (v == f || v == big[u])continue;dfs1(v, u, false);}if (big[u]) {dfs1(big[u], u, true);}for (auto [v, e] : g[u]) {if (v == f || v == big[u])continue;for (int i = L[v]; i <= R[v]; i++) {add(w[node[i]]);}}add(w[u]);ans[edge_id[u]] = MAD();if (keep == false) {for (int i = L[u]; i <= R[u]; i++) {del(w[node[i]]);}}
}
void solve() {int n;cin >> n;for (int i = 1, u, v; i < n; ++i) {cin >> u >> v;g[v].pb({ u, i });g[u].pb({ v, i });}for (int i = 1; i <= n; ++i) {cin >> w[i];total[w[i]]++;if (total[w[i]] == 2)tmad.insert(w[i]);}dfs0(1, 0);dfs1(1, 0, false);for (int i = 1; i < n; ++i) {cout << ans[i] << endl;}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;// cin >> T;while (T--) {solve();}
}