Submission #42984308

---

Source Code Expand

// LUOGU_RID: 113367902
#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;
        }
        // cout << "# " << _Val.top().x << " " << _Val.top().y << " " << _Val.top().id << endl;
        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};
			// cout << "! " << t[j].x << endl;
			if (j != i) q.push(t[j]);//, cout << "+ " << j << endl;//, cout << "! " << j << " " << t[j].x << " " << t[j].y << " " << t[j].id << endl;
			ans += (ll) (n - 1) * ((int) v[j].size() - 2);
		}
		// cout << "> " << i << " " << n << " " << q.size() << " " << ans << endl;
		int s = 0;
		while (q.size()) {
			// if (++s > 450) {
			// 	while (q.size()) {
			// 		cout << q.top().x << " " << q.top().y << " " << q.top().id << endl;
			// 		q.pop();
			// 	}
			// 	return 0;
			// }
			int x = q.top().id;
			// cout << x << " " << t[x].x << " " << t[x].y << " " << t[x].id << endl;
			// cout << q.top().x << " " << q.top().y << " " << q.top().id << endl;
			// assert(q.top() == t[x]);
			// assert(t[x].id == x);
			// cout << "- " << x << endl;
			// cout << q.size() << " " << q.top().x << " " << q.top().y << " " << q.top().id << endl;
			q.pop();
			// cout << q.size() << " " << q.top().x << " " << q.top().y << " " << q.top().id << endl;
			int tx = find(far[x]);
			// cout << x << " " << tx << endl;
			if (tx != i) q.erase(t[tx]);//, cout << "-- " << tx << endl;
			ans -= (ll) t[tx].y * t[x].x;
			// cout << q.size() << " " << x << " " << t[tx].y << " " << t[x].x << endl;
			fa[x] = tx;
			t[tx].x += t[x].x;
			t[tx].y += t[x].y;
			if (tx != i) q.push(t[tx]);//, cout << "++ " << tx << endl;
		} chkmax(mx, ans);
		// cout << "! " << ans << endl;
	} cout << mx;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In member function ‘void heap<_Tp>::flush()’:
./Main.cpp:44:9: warning: this ‘while’ clause does not guard... [-Wmisleading-indentation]
   44 |         while(!_Del.empty() && !_Val.empty() && _Del.top() == _Val.top()) _Val.pop(), _Del.pop(); _Op = 0;
      |         ^~~~~
./Main.cpp:44:99: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘while’
   44 |         while(!_Del.empty() && !_Val.empty() && _Del.top() == _Val.top()) _Val.pop(), _Del.pop(); _Op = 0;
      |                                                                                                   ^~~
./Main.cpp: In member function ‘void heap<_Tp>::pop()’:
./Main.cpp:55:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   55 |         if(_Op) flush(); _Op = (!_Del.empty());
      |         ^~
./Main.cpp:55:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   55 |         if(_Op) flush(); _Op = (!_Del.empty());
      |                          ^~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:94:7: warning: unused variable ‘s’ [-Wunused-variable]
   94 |   int s = 0;
      |       ^

Judge Result