#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
int par[MAXN],n,depth[MAXN];
vector<int>g[MAXN];
vector<int>cycle;
bool vis[MAXN];
bool found;
int x1,x2;
int cycle_size;
void find_cycle(int u,int p)
{
par[u]=p;
for(auto xd:g[u])
{
if(par[xd]==0)
{
depth[xd]=depth[u]+1;
find_cycle(xd,u);
}
else
{
x1=u;
x2=xd;
}
}
}
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;
}
}
pair<int,int> maxd[MAXN];
pair<int,int> calc(int u)
{
vis[u]=1;
pair<int,int> ret={0,1};
for(auto xd:g[u])
{
if(vis[xd])continue;
pair<int,int> 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;
}
pair<int,int>maxdist;
int ans;
int val1[MAXN],val2[MAXN];
map<int,int> mp1,mp2;
int main()
{
maxdist={0,0};
cin>>n;
for(int i=1;i<=n;i++)
{
int 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(int i=0;i<cycle_size;i++)
{
cycle.push_back(cycle[i]);
}
int t=cycle_size/2;
for(int i=1;i<=cycle_size;i++)
{
vis[cycle[i]]=1;
}
for(int i=1;i<=cycle_size;i++)
{
calc(cycle[i]);
}
set<int>s1,s2;
for(int i=0;i<cycle_size*2;i++)
{
val1[i]=-i+maxd[cycle[i]].first;
val2[i]=i+maxd[cycle[i]].first;
}
for(int i=0;i<t;i++)
{
s1.insert(val1[i]);
mp1[val1[i]]+=maxd[cycle[i]].second;
s2.insert(val2[t+1+i]);
mp2[val2[i]]+=maxd[cycle[t+1+i]].second;
}
int max1=(*s1.rbegin()),max2=(*s2.rbegin());
int cnt,dist;
cnt=mp1[max1]*maxd[cycle[t]].second;
dist=max1+t+maxd[cycle[t]].first;
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;
if(dist>maxdist.first)
{
maxdist.first=dist;
maxdist.second=0;
}
if(dist==maxdist.first)
{
maxdist.second+=cnt;
}
for(int mid=t+1;mid+t<2*cycle_size;mid++)
{
s1.erase(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+t+maxd[cycle[mid]].first;
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;
if(dist>maxdist.first)
{
maxdist.first=dist;
maxdist.second=0;
}
if(dist==maxdist.first)
{
maxdist.second+=cnt;
}
}
ans=maxdist.second;
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
10624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
