제출 #887715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887715		beaboss	Hard route (IZhO17_road)	C++17	0 / 100	3 ms	15284 KiB

road

// Source: https://oj.uz/problem/view/IZhO17_road
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

const ll N = 5e5 + 10;

vi adj[N];
ll d[N], cnt[N];
pii out[N];

void dfs(ll cur, ll p = -1) {
	if (adj[cur].size() == 1)cnt[cur]=1;

	for (auto val: adj[cur]) {
		if (val != p) {
			dfs(val, cur);
			if (ckmax(d[cur], d[val] + 1)) {
				cnt[cur] = cnt[val];
			} else if (d[cur] == d[val] + 1) cnt[cur] += cnt[val];

		}
	}
}

ll mx = 0;
ll tot = 0;

void dfs2(ll cur, ll p = -1) {
	vpii leaf;
	leaf.pb(out[cur]);

	for (auto val: adj[cur]) {
		if (val != p) leaf.pb({d[val]+1, cnt[val]});
	}

	sort(leaf.rbegin(), leaf.rend());

	if (leaf.size() >= 3 && leaf[0].f * (leaf[1].f + leaf[2].f) >= mx) {
		ll res = 0;
		ll eq3 = 0;
		ll hardness = leaf[0].f * (leaf[1].f + leaf[2].f);

		for (auto val: leaf) if (val.f == leaf[2].f) eq3+=val.s;

		if (leaf[1].f == leaf[2].f) {
			res = eq3*eq3;
			for (auto val: leaf) if (val.f==leaf[2].f) res -= val.s*val.s;
			res /= 2;
		} else if (leaf[0].f == leaf[1].f) {
			res = eq3*(leaf[1].s+leaf[0].f);
		} else {
			res = eq3 * leaf[1].s;
		}

		if (ckmax(mx, hardness)) tot = res;
		else if (mx == hardness) tot += res;
	}


	ll num1 = 0;
	ll num2 = 0;
	for (auto val: adj[cur]) {
		if (d[val] + 1 == leaf[0].f) num1+=cnt[val];
		if (d[val] + 1 == leaf[1].f) num2+=cnt[val]; 
	}

	if (out[cur].f == leaf[0].f) num1 += out[cur].s;
	if (out[cur].f == leaf[1].f) num2 += out[cur].s;


	for (auto val: adj[cur]) {
		if (val != p) {
			if (d[val] + 1 == leaf[0].f && leaf[0].f == leaf[1].f ) out[val] = {leaf[1].f+1, num1 - cnt[val]};
			else if (d[val] + 1 == leaf[0].f) out[val] = {leaf[1].f + 1, num2};
			else out[val] = {leaf[0].f + 1, num1};

			dfs2(val, cur);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n;
	cin >> n;

	FOR(i, 1, n) {
		ll a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	out[1].s=1;
	dfs(1);
	dfs2(1);

	if (mx == 0 && tot == 0) tot=1;

	cout << mx << ' ' << tot << endl;



}

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