Submission #1268937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268937		g4yuhg	Hard route (IZhO17_road)	C++20	0 / 100	2 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 400005
#define LOG 19
#define endl '\n'
using namespace std;

bool ghuy4g;

ll n, mx[N][3], kq[N], leaf;
vector<ll> adj[N];

ll ans = 0, cnt = 0;

void dfs(ll u, ll parent) {
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dfs(v, u);
		mx[v][0] ++ ;
		if (mx[v][0] >= mx[u][0]) {
			mx[u][2] = mx[u][1];
			mx[u][1] = mx[u][0];
			mx[u][0] = mx[v][0];
		}
		else if (mx[v][0] >= mx[u][1]) {
			mx[u][2] = mx[u][1];
			mx[u][1] = mx[v][0];
		}
		else if (mx[v][0] > mx[u][2]){
			mx[u][2] = mx[v][0];
		}
		mx[v][0] -- ;
	}
}

void dfs1(ll u, ll parent, ll len) {
	vector<ll> vt;
	if (len > 0) vt.push_back(len);
	for (int i = 0; i < 3; i ++) {
		if (mx[u][i] > 0) {
			vt.push_back(mx[u][i]);
		}
	}
	sort(vt.begin(), vt.end(), greater<ll>());
	
	/*cout << "_____ " << u << " | " << endl;
	for (auto it : vt) cout << it << " ";
	cout << endl;
	cout << "ans " << ans << endl;*/
	
	if (adj[u].size() > 1) {
	
		for (int i = 0; i < vt.size(); i ++) {
			ll res = vt[i];
			if (vt[i] == 0) continue;
			for (int j = 0; j < vt.size(); j ++) {
				if (j == i) continue;
				if (vt[j] == 0) continue;
				for (int z = j + 1; z < vt.size(); z ++) {
					if (z == i) continue;
					if (vt[z] == 0) continue;
					res = vt[i] * (vt[j] + vt[z]);
					if (res == 6) {
						//cout << i << " " << j << " " << z << endl;
						//cout << vt[i] << " here " << vt[j] << " " << vt[z] << endl;
					}
					if (res > ans) {
						ans = res;
						cnt = 0;
					}
					if (res == ans) {
						cnt ++ ;
					}
				}
			}
		}
	
	}
	else {
		leaf ++ ;
	}
	
	for (auto v : adj[u]) {
		if (v == parent) continue;
		ll new_len = len + 1;
		if (mx[u][0] - 1 == mx[v][0]) {
			new_len = max(new_len, mx[u][1] + 1);
		}
		else {
			new_len = max(new_len, mx[u][0] + 1);
		}
		dfs1(v, u, new_len);
	}
}

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);
    }
    
    dfs(1, 1);
    dfs1(1, 1, 0);
    
    if (ans == 0) {
    	cout << ans << " " << leaf * (leaf - 1) / 2;
    	return 0;
    }
    
    cout << ans << " " << cnt;
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

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