Submission #1114483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114483		VectorLi	Hard route (IZhO17_road)	C++17	100 / 100	667 ms	192656 KiB

road

#include <bits/stdc++.h>
#define I64 long long

using namespace std;

const int N = (int) 5E5;

struct node {
	int d;
	I64 x;
	friend bool operator < (node u, node v) {
		return u.d > v.d;
	}
};

void merge(node &u, node v) {
	if (u.d < v.d) {
		u = v;
	} else if (u.d == v.d) {
		u.x = u.x + v.x;
	}
}

int n;
vector<int> e[N];

int p[N];
node f[N], g[N];

I64 best = 0, total = 1;

void DFS1(int u) {
	if (p[u] >= 0) {
		e[u].erase(find(e[u].begin(), e[u].end(), p[u]));
	}
	f[u] = {0, 1};
	for (auto v : e[u]) {
		p[v] = u;
		DFS1(v);
		merge(f[u], {f[v].d + 1, f[v].x});
	}
}

void DFS2(int u) {
	int c = (int) e[u].size();
	vector<node> a;
	
	if (p[u] >= 0 || c == 1) {
		a.push_back(g[u]);
	}
	for (auto v : e[u]) {
		a.push_back({f[v].d + 1, f[v].x});
	}
	sort(a.begin(), a.end());
	
	if ((int) a.size() >= 3) {
		int d[3] = {a[0].d, a[1].d, a[2].d};
		I64 x[3] = {a[0].x, a[1].x, a[2].x};
		I64 t = 0;
		I64 current = (I64) d[0] * (d[1] + d[2]), number = 0;
		
		for (int i = 0; i < (int) a.size(); i++) {
			if (a[i].d == d[2]) {
				t = t + a[i].x;
			}
		}
		
		if (d[0] > d[1] && d[1] > d[2]) {
			number = x[1] * t;
		}
		if (d[0] > d[1] && d[1] == d[2]) {
			number = t * t;
			for (int i = 0; i < (int) a.size(); i++) {
				if (a[i].d == d[2]) {
					number = number - a[i].x * a[i].x;
				}
			}
			number = number / 2;
		}
		if (d[0] == d[1] && d[1] > d[2]) {
			number = (x[0] + x[1]) * t;
		}
		if (d[0] == d[1] && d[1] == d[2]) {
			number = t * t;
			for (int i = 0; i < (int) a.size(); i++) {
				if (a[i].d == d[2]) {
					number = number - a[i].x * a[i].x;
				}
			}
			number = number / 2;
		}
		
		if (current > best) {
			best = current;
			total = number;
		} else if (current == best) {
			total = total + number;
		}
	} 
	
	vector<node> prefix(c), suffix(c);
	for (int i = 0; i < c; i++) {
		int v = e[u][i];
		prefix[i] = {f[v].d + 1, f[v].x};
		suffix[i] = {f[v].d + 1, f[v].x}; 
	}
	for (int i = 1; i < c; i++) {
		merge(prefix[i], prefix[i - 1]);
	} 
	for (int i = c - 2; i >= 0; i--) {
		merge(suffix[i], suffix[i + 1]);
	}
	for (int i = 0; i < c; i++) {
		int v = e[u][i];
		node t = g[u];
		if (i > 0) {
			merge(t, prefix[i - 1]);
		}
		if (i < c - 1) {
			merge(t, suffix[i + 1]);
		}
		g[v] = {t.d + 1, t.x};
		DFS2(v);
	}
}

void solve() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u = u - 1;
		v = v - 1;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	
	p[0] = 0 - 1;
	DFS1(0);
	
	g[0] = {0, 1};
	DFS2(0);
	cout << best << " " << total << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

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