#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,ll> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<PII>g[MAXN];
stack<int>st;
vector<int>adj[MAXN],v;
int vis[MAXN];
void dfs1(int nd,int pr){
if(!v.empty())
return;
if(vis[nd]){
while(!st.empty() and st.top()!=nd)
v.pb(st.top()),st.pop();
v.pb(nd);
return;
}
st.push(nd);
vis[nd]=1;
tr(it,g[nd])
if(it->ss!=pr)
dfs1(it->ff,it->ss);
if(!st.empty())
st.pop();
}
PII dp[MAXN],ans;
PII merge(PII x,PII y){
if(x.ff>y.ff)
return x;
if(y.ff>x.ff)
return y;
return mp(x.ff,x.ss+y.ss);
}
void dfs(int nd,int pr){
dp[nd]=mp(0,1);
vector<PII>v;
tr(it,adj[nd])
if(*it!=pr and !vis[*it]){
dfs(*it,nd);
v.pb(dp[*it]);
dp[nd]=merge(dp[nd],dp[*it]);
}
sort(all(v));
if(int(v.size())>=2){
PII b=v[v.size()-2],a=v[v.size()-1],c=mp(a.ff+b.ff,0);
for(int i=0;i<int(v.size());i++)
if(v[i].ff==b.ff)
c.ss+=v[i].ss;
if(a.ff!=b.ff){
c.ss*=a.ss;
ans=merge(ans,c);
}
else{
c.ss*=c.ss;
for(int i=0;i<int(v.size());i++)
if(v[i].ff==b.ff)
c.ss-=v[i].ss*v[i].ss;
c.ss/=2;
ans=merge(ans,c);
}
}
else
ans=merge(ans,dp[nd]);
dp[nd].ff++;
}
map<int,ll>a;
int main(){
//freopen("in", "r", stdin);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].pb(mp(v,i));adj[u].pb(v);
g[v].pb(mp(u,i));adj[v].pb(u);
}
dfs1(1,-1);int sz=int(v.size());
memset(vis,0,sizeof vis);
tr(it,v)
vis[*it]=1;
vector<PII>g;
tr(it,v)
dfs(*it,-1),g.pb(mp(dp[*it].ff-1,dp[*it].ss));
int p=0;
for(int i=0;i<sz;i++){
while(p+p<=sz+i+i)
a[g[p].ff+p]+=g[p].ss,p++;
a[g[i].ff+i]-=g[i].ss;
if(!a[g[i].ff+i])
a.erase(g[i].ff+i);
PII tmp=*a.rbegin();
ans=merge(ans,mp(tmp.ff+g[i].ff-i,tmp.ss*tmp.ss));
}p=sz-1;a.clear();
for(int i=sz-1;i>=0;i--){
while(p+p>=sz+i+i)
a[g[p].ff+sz-p]+=g[p].ss,p--;
PII tmp=*a.rbegin();
ans=merge(ans,mp(tmp.ff+g[i].ff+i,tmp.ss*tmp.ss));
}
printf("%lld\n",ans.ss);
return 0;
}
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
85 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
shymbulak.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
88 | scanf("%d%d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
21100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
21400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
41604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
