#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;
int imp2(int x)
{
if(x<0)
return -1;
return x/2;
}
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]];
//cout<<i<<" "<<cyc[i]<<" "<<maxd[cyc[i]]<<" "<<cntmax[cyc[i]]<<" zzz\n";
}
build(1,0,(int)cyc.size()-1);
for(int i=1;i<cyc.size();i++)
{
pair<int,int> x = qry(1,0,(int)cyc.size()-1, max(0LL,imp2(2*i - (int)cyc.size() + 1)), i-1, 0);
x.first += i + maxd[cyc[i]];
if(x.first > maxdist)
{
maxdist = x.first;
cate = x.second * cntmax[cyc[i]];
}
else if(x.first == maxdist)
cate += x.second * cntmax[cyc[i]];
//cout<<i<<" "<<cyc[i]<<" "<<imp2(2*i - (int)cyc.size())<<" zzz\n";
x = qry(1,0,(int)cyc.size()-1,0,min(i-1, imp2(2*i - (int)cyc.size())), 1);
x.first += (int)cyc.size()-1-i + 1 + maxd[cyc[i]];
if(x.first > maxdist)
{
maxdist = x.first;
cate = x.second * cntmax[cyc[i]];
}
else if(x.first == maxdist)
cate += x.second * cntmax[cyc[i]];
}
//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:152: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]
152 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp:168: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]
168 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:199: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]
199 | for(int i=0;i<cyc.size();i++)
| ~^~~~~~~~~~~
shymbulak.cpp:213: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]
213 | for(int i=1;i<cyc.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14684 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14768 KB |
Output is correct |
| 5 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 6 |
Correct |
2 ms |
14928 KB |
Output is correct |
| 7 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 8 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 9 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 10 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 11 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 12 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 13 |
Correct |
2 ms |
14684 KB |
Output is correct |
| 14 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 15 |
Correct |
3 ms |
14936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 5 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 6 |
Correct |
4 ms |
15168 KB |
Output is correct |
| 7 |
Correct |
5 ms |
14940 KB |
Output is correct |
| 8 |
Correct |
5 ms |
14940 KB |
Output is correct |
| 9 |
Correct |
5 ms |
14896 KB |
Output is correct |
| 10 |
Correct |
4 ms |
14940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
18952 KB |
Output is correct |
| 2 |
Correct |
62 ms |
18756 KB |
Output is correct |
| 3 |
Correct |
65 ms |
25548 KB |
Output is correct |
| 4 |
Correct |
55 ms |
18516 KB |
Output is correct |
| 5 |
Correct |
55 ms |
18664 KB |
Output is correct |
| 6 |
Correct |
131 ms |
22444 KB |
Output is correct |
| 7 |
Correct |
87 ms |
20304 KB |
Output is correct |
| 8 |
Correct |
117 ms |
22356 KB |
Output is correct |
| 9 |
Correct |
119 ms |
22356 KB |
Output is correct |
| 10 |
Correct |
115 ms |
25172 KB |
Output is correct |
| 11 |
Correct |
110 ms |
28476 KB |
Output is correct |
| 12 |
Correct |
116 ms |
28064 KB |
Output is correct |
