#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second
#define ar array
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
//#define
const int M=1e9+7;
const int N=5e5+4;
const int inf=N;
struct fck{
int val=-N;
ll cl=0;
fck(){
val=-N;cl=0;
}
};
void mg(fck &a,fck b){
if(a.val<b.val) a=b;
else if(a.val==b.val){
a.cl+=b.cl;
}
}
fck dpd[N],dpu[N];
vec<fck>go[N];
vec<int>g[N];
ll ans1=0;
ll ans2=0;
/// a<=b<=c c*(a+b)
void dfs1(int v,int p){
dpd[v].val=0,dpd[v].cl=1;
go[v].resize(sz(g[v]));
for(int i=0;i<sz(g[v]);i++){
int z=g[v][i];
if(z==p) continue;
dfs1(z,v);
auto lel=dpd[z];
lel.val++;
go[v][i]=lel;
mg(dpd[v],lel);
}
}
void dfs2(int v,int p,fck from){
vec<int>sons;
for(int i=0;i<sz(g[v]);i++){
int z=g[v][i];
if(z==p){
go[v][i]=from;
}
else{
sons.pb(z);
}
}
int n=sz(sons);
vec<fck>pref(n);
vec<fck>suf(n);
{
fck cr;
for(int i=0;i<n;i++){
pref[i]=cr;
fck lel=dpd[sons[i]];lel.val++;
mg(cr,lel);
}
}
{
fck cr;
for(int i=n-1;i>=0;i--){
suf[i]=cr;
fck lel=dpd[sons[i]];lel.val++;
mg(cr,lel);
}
}
for(int i=0;i<sz(sons);i++){
int u=sons[i];
fck lel=from;
mg(lel,pref[i]);mg(lel,suf[i]);
lel.val++;
dfs2(u,v,lel);
}
}
void ins(vec<ll> &vl,ll x){
for(int i=2;i>=0;i--){
if(vl[i]==x) break;
if(vl[i]<x) swap(vl[i],x);
}
}
void dfs3(int v,int p){
for(auto &z : g[v]){
if(z==p) continue;
dfs3(z,v);
}
if(sz(g[v])<=2) return;
vec<vec<int>>prek(3,vec<int>());
vec<ll>value(3,-2);
for(int i=0;i<sz(g[v]);i++){
ll x=go[v][i].val;
ins(value,x);
}
for(int i=0;i<sz(g[v]);i++){
for(int j=0;j<3;j++){
if(value[j]==go[v][i].val){
prek[j].pb(go[v][i].cl);
}
}
}
vec<ll>dp(4,0);
ll x=-1;
vec<int>to;
if(sz(prek[2])==1){
if(sz(prek[1])>1){
dp[1]=1;
x=value[2]*(value[1]+value[1]);
to=prek[1];
}
else if(sz(prek[1])==1 && sz(prek[0])){
dp[2]=prek[1][0];
to=prek[0];
x=value[2]*(value[1]+value[0]);
}
}
else if(sz(prek[2])==2){
dp[2]=prek[2][0]+prek[2][1];
to=prek[1];
if(sz(to))x=1ll*value[2]*(value[2]+value[1]);
}
else if(sz(prek[2])>2){
dp[1]=1;
to=prek[2];
if(sz(to))x=1ll*value[2]*(value[2]+value[2]);
}
for(auto &z : to){
dp[3]+=1ll*dp[2]*z;
dp[2]+=1ll*dp[1]*z;
}
if(x>ans1) ans1=x,ans2=dp[3];
else if(x==ans1) ans2+=dp[3];
// cerr<<v+1<<' '<<x<<' '<<ans2<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ifstream cin("road.in");
ofstream cout("road.out");
int n;
cin>>n;
for(int i=1;i<n;i++){
int v,u;
cin>>v>>u;--v;--u;
g[v].pb(u);g[u].pb(v);
}
int root=-1;
for(int i=0;i<n;i++){
if(sz(g[i])>2) root=i;
}
if(root==-1){
cout<<0<<' '<<1;
///just line;
return 0;
}
dfs1(root,root);
fck blya;
assert(blya.val==-inf);
dfs2(root,root,blya);
dfs3(root,root);
cout<<ans1<<' '<<ans2;
return 0;
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7
4
1 2
2 3
2 4
5
1 2
2 3
3 4
4 5
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
39372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
39372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
39372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
