【大联盟】20230626 集查并（dsu） 题解 AT_toyota2023spring_final_g 【Git Gud】

【大联盟】20230626 集查并（dsu） 题解 AT_toyota2023spring_final_g 【Git Gud】

zyx /bx

题目描述

here

题解

由于这场出了 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;
}