#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=500000;
vector<I>adjs[N];
I dp1[N],dp2[N];
vector<I>curs;
I cnts[N];
pair<Lli,Lli>res={0,1};
void dfs1(I a,I p=-1){
for(auto b:adjs[a])if(b!=p){
dfs1(b,a);
dp1[a]=max(dp1[a],dp1[b]+1);
}
}
void dfs2(I a,I p=-1){
I low=dp2[a];
for(auto b:adjs[a])if(b!=p){
dp2[b]=max(dp2[b],low+1);
low=max(low,dp1[b]+1);
}
reverse(adjs[a].begin(),adjs[a].end());
low=dp2[a];
for(auto b:adjs[a])if(b!=p){
dp2[b]=max(dp2[b],low+1);
low=max(low,dp1[b]+1);
}
curs.clear(),curs.push_back(dp2[a]);
for(auto b:adjs[a])if(b!=p)curs.push_back(dp1[b]+1);
if(curs.size()>=3){
sort(curs.rbegin(),curs.rend());
Lli x=curs[0],y=curs[1],z=curs[2];
for(auto i:curs)cnts[i]++;
Lli val=x*(y+z),cnt=1;
cnt*=cnts[x];
cnt*=cnts[y]-(y==x);
cnt*=cnts[z]-(z==x)-(z==y);
if(y==z)cnt/=2;
if(val>res.first)res={val,0};
if(val==res.first)res.second+=cnt;
for(auto i:curs)cnts[i]--;
}
for(auto b:adjs[a])if(b!=p)dfs2(b,a);
}
I main(){
cin.tie(0)->sync_with_stdio(0);
I n;cin>>n;
for(I i=0;i<n-1;i++){
I u,v;cin>>u>>v,u--,v--;
adjs[u].push_back(v);
adjs[v].push_back(u);
}
dfs1(0),dfs2(0);
auto[val,cnt]=res;
printf("%lli %lli\n",val,cnt);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11976 KB |
Output is correct |
3 |
Correct |
7 ms |
12036 KB |
Output is correct |
4 |
Incorrect |
7 ms |
12084 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11976 KB |
Output is correct |
3 |
Correct |
7 ms |
12036 KB |
Output is correct |
4 |
Incorrect |
7 ms |
12084 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11976 KB |
Output is correct |
3 |
Correct |
7 ms |
12036 KB |
Output is correct |
4 |
Incorrect |
7 ms |
12084 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |