Explanation

Assume there is some hard route that goes from vertex $u$ to vertex $v$. Let the node that the path from $u$ to $v$ and the furthest node from the hard route meet be node $x$. Use rerooting DP to calculate the hardest route and the number of such hardest routes for every node $x$.

Implementation

Time Complexity: $\mathcal{O}(N\log{N})$

Copy
#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;