제출 #966405

#제출 시각아이디문제언어결과실행 시간메모리
966405eysbutnoHard route (IZhO17_road)C++17
100 / 100
847 ms178100 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<vector<int>> adj(n);
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	vector<int> max_length(n), path_count(n);
	function<void(int, int)> dfs = [&](int u, int p) {
		/**
		 * Calculates the longest path from vertex u,
		 * and the number of such paths.
		 */
		max_length[u] = 0;
		path_count[u] = 1;
		for (int v : adj[u])
			if (v != p) {
				dfs(v, u);
				if (max_length[u] < max_length[v] + 1) {
					max_length[u] = max_length[v] + 1;
					path_count[u] = path_count[v];
				} else if (max_length[v] + 1 == max_length[u]) {
					path_count[u] += path_count[v];
				}
			}
	};
	dfs(0, -1);

    ll max_hardness = 0;
    ll hardest_path_count = 1; 
	function<void(int, int, ll, ll)> dfs2 = [&](int u, int p, ll parDist,
	                                            ll parCnt) {
		/**
		 * Performs the rerooting, to count the hardest
		 * path and the # of such paths at this vertex.
		 */
		vector<array<ll, 2>> paths;  // {distance, count}
		if (u > 0 || (int)adj[u].size() == 1) {
			paths.push_back({parDist, parCnt});
		}
		for (int v : adj[u])
			if (v != p) { paths.push_back({max_length[v] + 1, path_count[v]}); }
		sort(paths.begin(), paths.end(), greater<>());

		if ((int)adj[u].size() >= 3) {  // can form a nonzero hardness route
			/**
			 * Let the 3 longest path lengths be a, b, c, with a > b > c.
			 * The optimal hard route "hardness" is a * (b + c).
			 */
			ll a = paths[0][0];
            ll b = paths[1][0];
            ll c = paths[2][0];
			ll cur = a * (b + c);
            ll num = 0;
            ll ties = 0;
			for (auto [len, cnt] : paths) {
				if (len == c) ties += cnt;
			}

            if (a != b && b != c) {
                // case 1: all are distinct.
                num = paths[1][1] * ties;
            } else if (a == b && b == c) {
                // case 2: all are the same.
                num = ties * ties;
				for (auto [len, cnt] : paths) {
					if (len == a) num -= cnt * cnt;
				}
				num /= 2; // avoiding double counting
            } else if (a == b) {
                // case 3: first two are the same.
                num = (paths[0][1] + paths[1][1]) * ties;
            } else {
                // case 4: last two are the same.
               	num = ties * ties;
				for (auto [len, cnt] : paths) {
					if (len == c) num -= cnt * cnt;
				}
				num /= 2; // avoiding double counting
            }

            if (max_hardness < cur) {
                max_hardness = cur;
                hardest_path_count = num;
            } else if (max_hardness == cur) {
                hardest_path_count += num;
            }
        }
        // processing parent dist and parent count.
        ll longest1 = 0;
        ll longest2 = 0;
        ll count1 = 0;
        ll count2 = 0;
        for (auto [len, cnt] : paths) {
            if (len + 1 > longest1) {
                swap(longest1, longest2);
                swap(count1, count2);
                longest1 = len + 1;
                count1 = cnt;
            } else if (len + 1 == longest1) {
                count1 += cnt;
            } else if (len + 1 > longest2) {
                longest2 = len + 1;
                count2 = cnt;
            } else if (len + 1 == longest2) {
                count2 += cnt;
            }
        }
        for (int v : adj[u]) if (v != p) {
            // using the best parent hardness and parent count possible.
            if (max_length[v] + 2 == longest1) {
                (path_count[v] == count1) ? dfs2(v, u, longest2, count2) :
                            	            dfs2(v, u, longest1, count1 - path_count[v]);
            } else {
                dfs2(v, u, longest1, count1);
            }
        }
    }; 
    dfs2(0, -1, 0, 1);
    
    cout << max_hardness << ' ' << hardest_path_count << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...