Submission #599680

#	Time	Username	Problem	Language	Result	Execution time	Memory
599680		GusterGoose27	Hard route (IZhO17_road)	C++11	100 / 100	845 ms	229692 KiB

road

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 5e5;
int n;
vector<int> edges[MAXN];
pii dist[MAXN];
pii p_dist[MAXN];
ll best_h = 0;
ll num_ways = 1;

void upd(ll v, ll c) {
	if (v == best_h) num_ways += c;
	else if (v > best_h) {
		best_h = v;
		num_ways = c;
	}
}

void dfs(int cur, int p = -1) {
	dist[cur] = pii(0, 1);
	for (int next: edges[cur]) {
		if (next == p) continue;
		dfs(next, cur);
		pii ndist = dist[next];
		if (ndist.first == dist[cur].first-1) dist[cur].second += ndist.second;
		if (ndist.first >= dist[cur].first) {
			dist[cur] = ndist;
			dist[cur].first++;
		}
	}
}

void dfs2(int cur, int p = -1) {
	map<int, int> curdists;
	curdists[p_dist[cur].first] = p_dist[cur].second;
	vector<pii> distlist;
	if (cur != 0) distlist.push_back(p_dist[cur]);
	for (int next: edges[cur]) {
		if (next != p) {
			curdists[dist[next].first+1] += dist[next].second;
			distlist.push_back(pii(dist[next].first+1, dist[next].second));
		}
	}
	for (int next: edges[cur]) {
		if (next == p) continue;
		curdists[dist[next].first+1] -= dist[next].second;
		if (curdists[dist[next].first+1] == 0) curdists.erase(dist[next].first+1);
		p_dist[next] = *(curdists.rbegin());
		p_dist[next].first++;
		curdists[dist[next].first+1] += dist[next].second;
		dfs2(next, cur);
	}
	sort(distlist.begin(), distlist.end());
	assert(distlist.size() == edges[cur].size());
	if (edges[cur].size() > 2) {
		int dsize = distlist.size();
		pii aval = distlist[dsize-1];
		pii bval = distlist[dsize-2];
		pii cval = distlist[dsize-3];
		if (aval.first == bval.first && aval.first == cval.first) {
			int pos = dsize-1;
			ll p = 0;
			ll q = 0;
			while (pos >= 0 && distlist[pos].first == aval.first) {
				p += distlist[pos].second;
				q += pow(distlist[pos].second, 2);
				pos--;
			}
			ll count = (p*p-q)/2;
			ll num = 2*aval.first;
			num *= aval.first;
			upd(num, count);
		}
		else if (aval.first == bval.first) {
			int pos = dsize-3;
			ll p = 0;
			while (pos >= 0 && distlist[pos].first == cval.first) {
				p += distlist[pos].second;
				pos--;
			}
			ll count = p*(bval.second+aval.second);
			ll num = aval.first+cval.first;
			num *= bval.first;
			upd(num, count);
		}
		else if (bval.first == cval.first) {
			int pos = dsize-2;
			ll p = 0;
			ll q = 0;
			while (pos >= 0 && distlist[pos].first == bval.first) {
				p += distlist[pos].second;
				q += pow(distlist[pos].second, 2);
				pos--;
			}
			ll count = (p*p-q)/2;
			ll num = 2*bval.first;
			num *= aval.first;
			upd(num, count);
		}
		else {
			int pos = dsize-3;
			ll p = 0;
			while (pos >= 0 && distlist[pos].first == cval.first) {
				p += distlist[pos].second;
				pos--;
			}
			ll count = p*bval.second;
			ll num = bval.first+cval.first;
			num *= aval.first;
			upd(num, count);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	dfs(0);
	p_dist[0] = pii(0, 1);
	dfs2(0);
	cout << best_h << " " << num_ways << "\n";
}

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