#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=5e5+29;
ll n,ans,cnt=1,d[N],c[N];
vector<ll>g[N];
void dfs(ll v,ll pr=0){
d[v]=1;
c[v]=1;
for(ll to:g[v]){
if(to==pr)continue;
dfs(to,v);
if(d[to]+1==d[v])c[v]+=c[to];
if(d[to]+1>d[v]){
d[v]=d[to]+1;
c[v]=c[to];
}
}
}
bool cmp(ll a, ll b){
return d[a]>d[b];
}
void solve(ll x){
dfs(x);
sort(g[x].begin(),g[x].end(),&cmp);
for(ll j=0;j<g[x].size();j++){
for(ll k=j+1;k<g[x].size();k++){
for(ll i=0;i<g[x].size();i++){
if(i==j||i==k)continue;
ll a=g[x][i],b=g[x][j],cc=g[x][k];
if(d[a]*(d[b]+d[cc])==ans){
cnt+=c[b]*c[cc];
break;
}
if(d[a]*(d[b]+d[cc])>ans){
ans=d[a]*(d[b]+d[cc]);
cnt=c[b]*c[cc];
break;
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(ll i=1;i<n;i++){
ll v,u;
cin>>v>>u;
g[v].push_back(u);
g[u].push_back(v);
}
for(ll i=1;i<=n;i++){
if(g[i].size()>=3){
solve(i);
}
}
cout<<ans<<" "<<cnt<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |