#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+6;
ll par[MAXN],n,depth[MAXN];
vector<ll>g[MAXN];
vector<ll>cycle;
bool vis[MAXN];
bool found;
ll x1,x2;
ll cycle_size;
pair<ll,ll> maxd[MAXN];
pair<ll,ll>maxdist;
void find_cycle(ll u,ll p)
{
par[u]=p;
for(auto xd:g[u])
{
if(par[xd]==0)
{
depth[xd]=depth[u]+1;
find_cycle(xd,u);
}
else if(xd!=par[u]&&!found)
{
x1=u;
x2=xd;
found=1;
}
}
}
void make_cycle()
{
if(depth[x1]<depth[x2])swap(x1,x2);
cycle.push_back(x1);
for(;;)
{
x1=par[x1];
cycle.push_back(x1);
if(x1==x2)break;
}
}
void dfs1(int u)
{
pair<int,int> ansu;
ansu={0,0};
vis[u]=1;
vector<pair<int,int> >farthest;
for(auto xd:g[u])
{
if(vis[xd])continue;
dfs1(xd);
farthest.push_back({maxd[xd].first+1,maxd[xd].second});
}
sort(farthest.rbegin(),farthest.rend());
map<int,int> mpmp;
if(farthest.size()>=2)
{
for(auto xd:farthest)mpmp[xd.first]+=xd.second;
ansu.first=farthest[0].first+farthest[1].first;
if(farthest[0].first==farthest[1].first)
{
for(int i=0;i<farthest.size();i++)
{
if(farthest[i].first!=farthest[0].first)break;
ansu.second+=farthest[i].second*(mpmp[farthest[i].first]-farthest[i].second);
}
}
else
{
ansu.second=mpmp[farthest[0].first]*mpmp[farthest[1].first];
}
}
//cout<<u<<" "<<ansu.first<<" "<<ansu.second<<endl;
if(ansu.first>maxdist.first)
{
maxdist.first=ansu.first;maxdist.second=0;
}
if(ansu.first==maxdist.first)
{
maxdist.second+=ansu.second;
}
}
pair<ll,ll> calc(ll u)
{
vis[u]=1;
pair<ll,ll> ret={0,1};
for(auto xd:g[u])
{
if(vis[xd])continue;
pair<ll,ll> f=calc(xd);
f.first++;
if(f.first==ret.first)ret.second+=f.second;
else if(f.first>ret.first)ret=f;
}
return maxd[u]=ret;
}
ll ans;
ll val1[2*MAXN],val2[2*MAXN];
map<ll,ll> mp1;
int main()
{
maxdist={0,0};
cin>>n;
for(ll i=1;i<=n;i++)
{
ll x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
find_cycle(1,-1);
make_cycle();
cycle_size=cycle.size();
for(ll i=0;i<cycle_size;i++)
{
//cout<<cycle[i]<<" ";
cycle.push_back(cycle[i]);
}
//cout<<endl;
ll t=cycle_size/2;
for(ll i=1;i<=cycle_size;i++)
{
vis[cycle[i]]=1;
}
for(ll i=1;i<=cycle_size;i++)
{
calc(cycle[i]);
}
multiset<ll>s1;
for(ll i=0;i<cycle_size*2;i++)
{
val1[i]=-i+maxd[cycle[i]].first;
val2[i]=i+maxd[cycle[i]].first;
}
for(ll i=0;i<t;i++)
{
s1.insert(val1[i]);
mp1[val1[i]]+=maxd[cycle[i]].second;
//s2.insert(val2[t+1+i]);
//mp2[val2[t+1+i]]+=maxd[cycle[t+1+i]].second;
}
/*for(int i=0;i<cycle.size();i++)
{
cout<<cycle[i]<<" ";
}
cout<<endl;*/
//cout<<t<<" "<<cycle[t]<<":\n";
ll max1=(*s1.rbegin());
//ll max2=(*s2.rbegin());
ll cnt,dist;
cnt=mp1[max1]*maxd[cycle[t]].second;
dist=max1+t+maxd[cycle[t]].first;
//cout<<dist<<" "<<cnt<<endl;
if(dist>maxdist.first)
{
maxdist.first=dist;
maxdist.second=0;
}
if(dist==maxdist.first)
{
maxdist.second+=cnt;
}
/*cnt=mp2[max2]*maxd[cycle[t]].second;
dist=max2-t+maxd[cycle[t]].first;
cout<<dist<<" "<<cnt<<endl;
if(dist>maxdist.first)
{
maxdist.first=dist;
maxdist.second=0;
}
if(dist==maxdist.first)
{
maxdist.second+=cnt;
}*/
for(ll mid=t+1;mid<cycle_size+t;mid++)
{
//cout<<mid<<" "<<cycle[mid]<<":\n";
s1.erase(s1.find(val1[mid-t-1]));
mp1[val1[mid-t-1]]-=maxd[cycle[mid-t-1]].second;
//s2.erase(val2[mid]);
//mp2[val2[mid]]-=maxd[cycle[mid]].second;
s1.insert(val1[mid-1]);
mp1[val1[mid-1]]+=maxd[cycle[mid-1]].second;
//s2.insert(val2[mid+t]);
//mp2[val2[mid+t]]+=maxd[cycle[mid+t]].second;
max1=(*s1.rbegin());
//max2=(*s2.rbegin());
cnt=mp1[max1]*maxd[cycle[mid]].second;
dist=max1+mid+maxd[cycle[mid]].first;
//cout<<dist<<" "<<cnt<<endl;
if(dist>maxdist.first)
{
maxdist.first=dist;
maxdist.second=0;
}
if(dist==maxdist.first)
{
maxdist.second+=cnt;
}
/*cnt=mp2[max2]*maxd[cycle[mid]].second;
dist=max2-mid+maxd[cycle[mid]].first;
cout<<dist<<" "<<cnt<<endl;
if(dist>maxdist.first)
{
maxdist.first=dist;
maxdist.second=0;
}
if(dist==maxdist.first)
{
maxdist.second+=cnt;
}
*/
/*cout<<"s1:\n";
for(auto xd:s1)cout<<xd<<" ";
cout<<endl;*/
}
//cout<<maxdist.first<<" "<<maxdist.second<<endl;
//ans=maxdist.second;
/*if(cycle_size%2==0)
{
for(ll i=0;i<t;i++)
{
ll j=i+t;
ll dist=maxd[cycle[i]].first+t+maxd[cycle[j]].first;
if(dist==maxdist.first)
{
ans+=maxd[cycle[i]].second*maxd[cycle[j]].second;
}
}
}*/
//cout<<ans<<endl;
memset(vis,0,sizeof(vis));
for(int i=0;i<cycle_size;i++)vis[cycle[i]]=1;
for(int i=0;i<cycle_size;i++)
{
dfs1(cycle[i]);
}
//cout<<maxdist.first<<" ";
cout<<maxdist.second<<endl;
return 0;
}
/*
8
1 2
2 3
2 4
2 5
2 8
3 6
6 4
4 7
*/
Compilation message
shymbulak.cpp: In function 'void dfs1(int)':
shymbulak.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<farthest.size();i++)
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5196 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5324 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
13280 KB |
Output is correct |
| 2 |
Correct |
121 ms |
13472 KB |
Output is correct |
| 3 |
Correct |
116 ms |
22324 KB |
Output is correct |
| 4 |
Correct |
95 ms |
13148 KB |
Output is correct |
| 5 |
Correct |
104 ms |
13192 KB |
Output is correct |
| 6 |
Correct |
282 ms |
20816 KB |
Output is correct |
| 7 |
Correct |
172 ms |
16860 KB |
Output is correct |
| 8 |
Correct |
193 ms |
21260 KB |
Output is correct |
| 9 |
Correct |
199 ms |
21460 KB |
Output is correct |
| 10 |
Correct |
184 ms |
22680 KB |
Output is correct |
| 11 |
Incorrect |
197 ms |
23948 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
