#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
const int INF = 1e9;
int n;
vector<int> con[200005];
bool visited[200005];
int parent[200005];
bool iscyc[200005];
int maxd[200005];
int cntmax[200005];
int depth[200005];
int tin[200005];
int tout[200005];
int timer;
bool gasit=0;
pair<int,int> capete;
int maxdist=0,cate=0;
vector<int> cyc;
pair<int,int> aint[530000][2];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
if(x.first > y.first)
return x;
if(x.first < y.first)
return y;
return {x.first, y.second + x.second};
}
void build(int nod, int st, int dr)
{
if(st==dr)
{
aint[nod][0] = {maxd[cyc[st]]-st, cntmax[cyc[st]]};
aint[nod][1] = {maxd[cyc[st]]+st, cntmax[cyc[st]]};
return;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
aint[nod][0] = combine(aint[nod*2][0], aint[nod*2+1][0]);
aint[nod][1] = combine(aint[nod*2][1], aint[nod*2+1][1]);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri, int c)
{
if(le>ri)
return {-INF,-1};
if(le==st && dr==ri)
return aint[nod][c];
int mij=(st+dr)/2;
return combine(qry(nod*2,st,mij,le,min(mij,ri),c),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,c));
}
bool isanc(int x, int y)
{
if(tin[x]<=tin[y] && tout[x]>=tout[y])
return 1;
return 0;
}
void dfs_find(int nod)
{
//if(gasit) return;
tin[nod]=++timer;
visited[nod]=1;
for(auto adj:con[nod])
{
if(!visited[adj])
{
parent[adj]=nod;
dfs_find(adj);
}
else if(adj!=parent[nod]) ///am gasit cyclu
{
if(gasit && (capete.first != adj || capete.second != nod))
{
while(1)
n=0;
}
gasit=1;
capete = {nod,adj};
}
}
tout[nod]=++timer;
}
void find_cycle()
{
dfs_find(1);
if(!gasit)
{
while(1)
n=0;
}
while(!isanc(capete.first,capete.second))
{
cyc.push_back(capete.first);
capete.first = parent[capete.first];
}
cyc.push_back(capete.first);
vector<int> aux;
while(capete.second!=capete.first)
{
aux.push_back(capete.second);
capete.second = parent[capete.second];
}
reverse(aux.begin(),aux.end());
for(auto x:aux)
cyc.push_back(x);
for(auto x:cyc)
iscyc[x]=1;
/*cout<<"cycle: ";
for(auto x:cyc)
cout<<x<<" ";
cout<<"\n";*/
}
void dfs2(int nod, int par)
{
maxd[nod] = depth[nod];
cntmax[nod] = 1;
vector<pair<int,int>> v;
for(auto adj:con[nod])
{
if(adj!=par && !iscyc[adj])
{
depth[adj]=depth[nod]+1;
dfs2(adj,nod);
v.push_back({maxd[adj] - depth[nod], cntmax[adj]});
if(maxd[adj]>maxd[nod])
{
maxd[nod] = maxd[adj];
cntmax[nod] = cntmax[adj];
}
else if(maxd[adj]==maxd[nod])
cntmax[nod] += cntmax[adj];
}
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if((int)v.size()>1 && v[0].first + v[1].first >= maxdist)
{
if(v[0].first==v[1].first)
{
int cntpref = v[0].second;
for(int i=1;i<v.size();i++)
{
if(v[i].first!=v[0].first)
break;
if(2*v[0].first > maxdist)
{
maxdist = 2*v[0].first;
cate = v[i].second * cntpref;
}
else if(2*v[0].first == maxdist)
cate += v[i].second * cntpref;
cntpref += v[i].second;
}
}
else
{
for(int i=1;i<v.size();i++)
{
if(v[i].first!=v[1].first)
break;
if(v[0].first + v[1].first > maxdist)
{
maxdist = v[0].first + v[1].first;
cate = v[i].second * v[0].second;
}
else if(v[0].first + v[1].first == maxdist)
cate += v[i].second * v[0].second;
}
}
}
}
signed main()
{
cin>>n;
int a,b;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if(a==b)
{
while(1)
n=0;
}
con[a].push_back(b);
con[b].push_back(a);
}
find_cycle();
for(int i=0;i<cyc.size();i++)
{
depth[cyc[i]]=0;
dfs2(cyc[i],0);
if(maxd[cyc[i]] > maxdist)
{
maxdist = maxd[cyc[i]];
cate = cntmax[cyc[i]];
}
else if(maxd[cyc[i]] == maxdist)
cate += cntmax[cyc[i]];
}
build(1,0,(int)cyc.size()-1);
for(int i=0;i<cyc.size();i++)
{
pair<int,int> x = qry(1,0,(int)cyc.size()-1, max(0LL,(2*i - (int)cyc.size()+1)/2), i-1, 0);
x.first += i+1;
if(x.first > maxdist)
{
maxdist = x.first;
cate = x.second;
}
else if(x.first == maxdist)
cate += x.second;
x = qry(1,0,(int)cyc.size()-1,0,min(i-1, (2*i - (int)cyc.size())/2), 1);
x.first += (int)cyc.size()-1-i + 1;
if(x.first > maxdist)
{
maxdist = x.first;
cate = x.second;
}
else if(x.first == maxdist)
cate += x.second;
}
// cout<<"maxdist: "<<maxdist<<"\n";
cout<<cate;
return 0;
}
/**
2*i < 2*j + cyc.size()
2*j > 2*i - cyc.size()
*/
Compilation message
shymbulak.cpp: In function 'void dfs2(long long int, long long int)':
shymbulak.cpp:147:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp:163:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:194:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(int i=0;i<cyc.size();i++)
| ~^~~~~~~~~~~
shymbulak.cpp:207:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(int i=0;i<cyc.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
18760 KB |
Output is correct |
| 2 |
Incorrect |
58 ms |
18748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
