#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
int n;
vector<int>komsu[200023];
int ans=0;
ll num=0;
int root[200023],dp[200023];
ll ways[200023];
int cycle(int pos,int las){
root[pos]=1;
for(int x:komsu[pos]){
if(x==las)continue;
if(root[x])return x;
int y=cycle(x,pos);
if(y==-1){
root[pos]=0;
return -1;
}
if(y){
if(y==pos)return -1;
return y;
}
}
root[pos]=0;
return 0;
}
void cal(int pos,int las){
ways[pos]=1;
for(int x:komsu[pos]){
if(x==las)continue;
if(root[x])continue;
cal(x,pos);
if(dp[x]+1+dp[pos]>ans){
num=0;
ans=dp[x]+1+dp[pos];
}
if(dp[x]+1+dp[pos]==ans){
num+=ways[x]*ways[pos];
}
if(dp[x]+1>dp[pos]){
dp[pos]=dp[x]+1;
ways[pos]=0;
}
if(dp[x]+1==dp[pos]){
ways[pos]+=ways[x];
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
komsu[x].pb(y);
komsu[y].pb(x);
}
cycle(1,1);
vector<int>v;
for(int i=1;i<=n;i++){
if(root[i]){
v.pb(i);
cal(i,i);
}
}
int cnt=v.size();
for(int i=0;i<cnt;i++){
v.pb(v[i]);
}
multiset<pair<int,ll>>st;
for(int i=1;i<cnt/2;i++){
st.insert({dp[v[i]]+i,ways[v[i]]});
}
for(int i=0;i<cnt;i++){
st.insert({dp[v[i+cnt/2]]+i+cnt/2,ways[v[i+cnt/2]]});
ll x=(--st.end())->fr-i+dp[v[i]],y=(--st.end())->sc*ways[v[i]];
if(ans<x){
ans=x;
num=0;
}
if(ans==x){
num+=y;
}
st.erase(st.find({dp[v[i+1]]+i+1,ways[v[i+1]]}));
}
cout<<num<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |