【大联盟】20230626 集查并（dsu） 题解 AT_toyota2023spring_final_g 【Git Gud】
zyx /bx
题目描述
题解
由于这场出了 T2、验了 T3（顺序是反的），所以赛时一直在想这个题，不过很遗憾不会。
相当有意思的题。
考虑合并两个点 \(x,y\) 时，对以后产生的贡献为 \(\max\{f_x,f_y\}\)，\(f_x\) 为 \(x\) 点当前剩下的度数，则合并出来的新点当前剩下的度数为 \(f_{new}=f_x+f_y-2\)。
这并不是一个好维护的形式，我们考虑初始时让每个点 \(f'(x)=f(x)-2\)，这样，每次合并就可以直接 \(f'(x)=f'(x)+f'(y)\)，每次算贡献的时候就是 \(\max\{f_x,f_y\}+2\)，感觉非常酷！
然后还有个结论：我们 merge 的顺序是按照一棵有根树来操作的，先操作根，再操作下面的点。有了这个加的限制就可以根据 典中典 Color a Tree 的做法来做了。
形式大概是第 \(i\) 次操作 \(x\)，贡献为 \(if_x\)。
证明大概就是调整法来证。
代码
记录。
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 2010;
int n, fa[N], far[N];
ll mx;
vector <int> v[N];
void dfs(int x, int fa) {
far[x] = fa;
for (int i: v[x])
if (i != fa) dfs(i, x);
}
struct Node {
int x, y, id;
inline friend bool operator < (const Node &x, const Node &y) {
if ((ll) x.x * y.y == (ll) y.x * x.y) return (x.id == y.id) ? x.y < y.y : x.id < y.id;
return (ll) x.x * y.y < (ll) y.x * x.y;
}
inline friend bool operator == (const Node &x, const Node &y) {
return x.x == y.x && x.y == y.y && x.id == y.id;
}
} t[N];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
template <typename _Tp> class heap {
priority_queue<_Tp> _Val, _Del; bool _Op; size_t _Siz;
void flush() {
while(!_Del.empty() && !_Val.empty() && _Del.top() == _Val.top()) _Val.pop(), _Del.pop(); _Op = 0;
}
public:
heap() : _Op(0), _Siz(0) {}
size_t size() {return _Siz;}
void push(const _Tp &x) {_Siz++; _Val.push(x);}
_Tp top() {
assert(_Siz); if(_Op) flush(); assert(!_Val.empty()); return _Val.top();
}
void pop() {
assert(_Siz); _Siz--;
if(_Op) flush(); _Op = (!_Del.empty());
assert(!_Val.empty()); _Val.pop();
}
bool empty() {return _Siz == 0;}
void erase(const _Tp &x) {
assert(_Siz); _Siz--;
if(_Op) flush(); assert(!_Val.empty());
if(x == _Val.top()) {
_Val.pop(); _Op = 1; return;
}
assert(x < _Val.top()); _Del.push(x);
}
void clear() {
_Op = _Siz = 0; priority_queue<_Tp> _Tx, _Ty;
swap(_Val, _Tx), swap(_Del, _Ty);
}
};
signed main() {
// freopen("dsu.in", "r", stdin);
// freopen("dsu.out", "w", stdout);
read(n);
F(i, 2, n) {
int x, y; read(x), read(y); x++, y++;
v[x].push_back(y);
v[y].push_back(x);
}
F(i, 1, n) {
dfs(i, 0);
heap <Node> q;
ll ans = 3 * (n - 1);
F(j, 1, n) {
fa[j] = j;
t[j] = {(int) v[j].size() - 2, 1, j};
if (j != i) q.push(t[j]);
ans += (ll) (n - 1) * ((int) v[j].size() - 2);
}
int s = 0;
while (q.size()) {
int x = q.top().id;
q.pop();
int tx = find(far[x]);
if (tx != i) q.erase(t[tx]);
ans -= (ll) t[tx].y * t[x].x;
fa[x] = tx;
t[tx].x += t[x].x;
t[tx].y += t[x].y;
if (tx != i) q.push(t[tx]);
} chkmax(mx, ans);
} cout << mx;
return 0;
}