题面描述
给定一颗树，求分成三部分后的最小差异值。
题解
暴力：每次枚举两个点，将其父边断掉，如果存在祖先关系则特判一下，复杂度 \(O(n^2)\)，预计 50pts。
正解：dfs 搜索每个结点，砍掉它的父边，剩下的尽量等分（易证）。
这一步可以用 multiset 维护。
对于一个点，将其到根节点的链上的点放入 \(s2\)，再将这条链左边的所有点放入 \(s1\)。
然后令 \(x= \dfrac{n-siz[u]}{2}\)。 在 \(s1\) 中查找最靠近 \(x\) 的两个数，在 \(s2\) 中查找最靠近 \(x+siz[u]\) 的两个数，四种情况讨论一下。
细节：dfs 到一个点时将其放入 \(s1\)，回溯的时候将其从 \(s1\) 中删除，并插入到 \(s2\) 中。
预计 100pts。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, siz[N], ans = 1e9;
vector<int> adj[N];
multiset<int> s, s2;
void dfs(int u, int lst) { //计算子树大小
siz[u] = 1;
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i]; if (v == lst) continue;
dfs(v, u); siz[u] += siz[v];
}
}
int getcha(int x, int y, int z) {return max(abs(x - y), max(abs(x - z), abs(y - z)));}
void dfs2(int u, int lst) {
if (u != 1) {
int tmp = n - siz[u], x;
x = tmp / 2;
multiset<int>::iterator it;
if (tmp > 1) {
it = s2.lower_bound(x + siz[u]);
if (it != s2.end()) ans = min(ans, getcha((*it) - siz[u], siz[u], n - (*it)));
it = s2.upper_bound(x + siz[u]);
if (it != s2.begin()) {
--it;
ans = min(ans, getcha((*it) - siz[u], siz[u], n - (*it)));
}
it = s.lower_bound(x);
if (it != s.end()) ans = min(ans, getcha((*it), siz[u], n - (*it) - siz[u]));
it = s.upper_bound(x);
if (it != s.begin()) {
--it;
ans = min(ans, getcha((*it), siz[u], n - (*it) - siz[u]));
}
}
}
if (u != 1) s2.insert(siz[u]); //点到根的链
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i]; if (v == lst) continue;
dfs2(v, u);
}
s.insert(siz[u]); //已经遍历完了的点
if (u != 1) s2.erase(s2.find(siz[u]));
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0); dfs2(1, 0);
cout << ans << endl;
return 0;
}