#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e3 + 10;
int dist[MAXN], dp[MAXN];
vector<int> adj[MAXN];
pair<int, int> ans;
void dfs_1(int v, int p){
dp[v] = 0;
for(auto u : adj[v]){
if(u != p){
dist[u] = dist[v] + 1;
dfs_1(u, v);
dp[v] = max(dp[v], dp[u] + 1);
}
}
}
void dfs_2(int v, int p, int max_dist){
if(adj[v].size() == 1 && v != p){
if(dist[v] * max_dist > ans.first){
ans = {dist[v] * max_dist, 1};
} else if(dist[v] * max_dist == ans.first) ans.second ++;
}
pair<int, int> max_prof = {0, 0};
for(auto u : adj[v]){
if(u != p){
if(dp[u] + 1 >= max_prof.first){
max_prof = {dp[u] + 1, max_prof.first};
} else max_prof.second = max(max_prof.second, dp[u] + 1);
}
}
for(auto u : adj[v]){
if(u != p){
int cur_dist = max_prof.first;
if(dp[u] + 1 == max_prof.first) cur_dist = max_prof.second;
dfs_2(u, v, cur_dist);
}
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
for(int i=1; i<n; i++){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=n; i++){
if(adj[i].size() == 1){
dist[i] = 0;
dfs_1(i, i);
dfs_2(i, i, 0);
}
}
cout << ans.first << " " << ans.second / 2 << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |