Submission #1269183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269183		g4yuhg	Hard route (IZhO17_road)	C++20	0 / 100	1 ms	328 KiB

road

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "mansion"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 200005
#define LOG 19
#define endl '\n'
using namespace std;

bool ghuy4g;

ll n;
vector<ll> adj[N];

ll d[N][2], c[N][2];

pii ans;

void dfs(ll u, ll parent) {
	vector<pii> vt;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dfs(v, u);
		//vt.push_back({d[v][0] + 1, c[v][0]});
		d[v][0] ++ ;
		if (d[v][0] >= d[u][0]) {
			d[u][1] = d[u][0];
			d[u][0] = d[v][0];
		}
		else if (d[v][0] >= d[u][1]) {
			d[u][1] = d[v][0];
		}
		d[v][0] -- ;
	}
	for (auto v : adj[u]) {
		if (v == parent) continue;
		if (d[v][0] + 1 == d[u][0]) {
			c[u][0] += c[v][0];
		}
		if (d[v][0] + 1 == d[u][1]) {
			c[u][1] += c[v][0];
		}
	}
	if (d[u][0] == 0) {
		c[u][0] = 1;
	}
	if (d[u][1] == 0) {
		c[u][1] = 1;
	}
}

void reroot(ll u, ll parent) {
	vector<pii> vt;
	for (auto v : adj[u]) {
		vt.push_back({d[v][0] + 1, c[v][0]});
	}
	pii cnt = {0, 0}; // cnt.fi la ket qua, cnt.se la so con dai bang con thu 2
	if (adj[u].size() >= 3) {
		sort(vt.begin(), vt.end(), greater<pii>());
		ll x = vt[0].fi * (vt[1].fi + vt[2].fi);
		for (pii it : vt) { 
			if (u == 2) {
				//cout << it.fi << " " << it.se << endl;
			}
			// ta dang thu chon con it nay la con thu 2
			// => no se gop voi cac con bang con thu nhat dang truoc
			// 0 = 1 = 2 van duoc, vi luon luon co 1 con lam nhanh dai nhat
			if (it.fi == vt[2].fi) {
				cnt.fi += cnt.se * it.se;
			}
			if (it.fi == vt[1].fi) {
				cnt.se += it.se;
			}
		}
		if (x > ans.fi) {
			ans.fi = x;
			ans.se = cnt.fi;
		}
		else if (x == ans.fi) {
			ans.se += cnt.fi;
		}
	}
	for (auto v : adj[u]) {
		if (v == parent) continue;
		ll dv0 = d[v][0], cv0 = c[v][0], du0 = d[u][0], cu0 = c[u][0], dv1 = d[v][1], cv1 = c[v][1];
		if (d[v][0] + 1 == d[u][0]) {
			if (c[v][0] == c[u][0]) { // nhanh to nhat la nhanh nay luon, khong co thu 2
				d[u][0] = d[u][1];
				c[u][0] = c[u][1];
			}
			else {
				c[u][0] -= c[v][0];
			}
		}
		if (d[u][0] + 1 >= d[v][0]) {
			d[v][1] = d[v][0]; c[v][1] = c[v][0];
			d[v][0] = d[u][0] + 1;
			c[v][0] = c[u][0];
		}
		reroot(v, u);
		d[v][0] = dv0, c[v][0] = cv0, d[u][0] = du0, c[u][0] = cu0, d[v][1] = dv1, c[v][1] = cv1;
	}
}

bool klinh;

signed main(void) {
    faster;
    
	cin >> n;
	for (int i = 1; i <= n - 1; i ++) {
		ll u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	ll r = 1;
	dfs(r, r);
	reroot(r, r);
	
	if (ans.fi == 0) ans.se = 1;
	
	cout << ans.fi << " " << ans.se;
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48