#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
int n;
vector<int> con[300005];
bool visited[300005];
int parent[300005];
bool iscyc[300005];
int maxd[300005];
int cntmax[300005];
int depth[300005];
int tin[300005];
int tout[300005];
int timer;
bool gasit=0;
pair<int,int> capete;
int maxdist=0,cate=0;
vector<int> cyc;
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
{
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);
reverse(cyc.begin(),cyc.end());
while(capete.second!=capete.first)
{
cyc.push_back(capete.second);
capete.second = parent[capete.second];
}
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],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());
for(int i=0;i<v.size();i++)
v[i].first = -v[i].first;
if((int)v.size()>1 && v[0].first + v[1].first >= maxdist)
{
if(v[0].first==v[1].first)
{
int ult = (int)v.size()-1;
for(int i=1;i<v.size();i++)
{
if(v[i]!=v[0])
{
ult = i-1;
break;
}
}
int cntpref=0;
for(int i=0;i<=ult;i++)
{
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
{
int ult = (int)v.size()-1;
for(int i=2;i<v.size();i++)
{
if(v[i]!=v[1])
{
ult = i-1;
break;
}
}
for(int i=1;i<=ult;i++)
{
if(v[0].first + v[1].first > maxdist)
{
maxdist = v[0].first + v[1].first;
cate = v[i].second * v[0].second;
}
else if(2*v[0].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;
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);
}
for(int i=0;i<cyc.size();i++)
{
for(int j=i+1;j<cyc.size();j++)
{
if(min(j-i,i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]] > maxdist)
{
maxdist = min(j-i,i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]];
if(j-i != i + 1 + (int)cyc.size()-1-j) cate = cntmax[cyc[i]] * cntmax[cyc[j]];
else cate = 2LL * cntmax[cyc[i]] * cntmax[cyc[j]];
}
else if(min(j-i,i + 1 + (int)cyc.size()-1-j) + maxd[cyc[i]] + maxd[cyc[j]] == maxdist)
{
if(j-i != i + 1 + (int)cyc.size()-1-j) cate += cntmax[cyc[i]] * cntmax[cyc[j]];
else cate += 2LL * cntmax[cyc[i]] * cntmax[cyc[j]];
}
}
}
// cout<<"maxdist: "<<maxdist<<"\n";
cout<<cate;
return 0;
}
Compilation message
shymbulak.cpp: In function 'void dfs2(long long int, long long int)':
shymbulak.cpp:96:18: 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]
96 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp:103: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]
103 | for(int i=1;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp:127: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]
127 | for(int i=2;i<v.size();i++)
| ~^~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:159: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]
159 | for(int i=0;i<cyc.size();i++)
| ~^~~~~~~~~~~
shymbulak.cpp:164: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]
164 | for(int i=0;i<cyc.size();i++)
| ~^~~~~~~~~~~
shymbulak.cpp:166:24: 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]
166 | for(int j=i+1;j<cyc.size();j++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19800 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19804 KB |
Output is correct |
| 3 |
Correct |
3 ms |
19804 KB |
Output is correct |
| 4 |
Correct |
3 ms |
19912 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
19916 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
19804 KB |
Output is correct |
| 2 |
Correct |
5 ms |
19916 KB |
Output is correct |
| 3 |
Correct |
4 ms |
19804 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
19892 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
27216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
