#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,ta,tb,p[201010],b[201010],CS,ma,jum,has,j,K;
vector<ll> v[201010],cyc,isi[201010],tom;
pair<ll,ll> A[201010],za[202020];
ll ST[2][1601601];
ll byk[2][1601601];
ll zx[202020];
ll zy[202020];
void dfs(ll aa)
{
b[aa]=1;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
{
if(v[aa][ii]==p[aa]||b[v[aa][ii]]==2)continue;
if(b[v[aa][ii]])
{
ll tem=aa;
cyc.pb(tem);
while(tem!=v[aa][ii])
{
tem=p[tem];
cyc.pb(tem);
}
}
else
{
p[v[aa][ii]]=aa;
dfs(v[aa][ii]);
}
}
b[aa]=2;
}
void dfs1(ll aa,ll bb,ll cc)
{
isi[i].pb(aa);
if(ma<cc)
{
ma=max(ma,cc);
jum=0;
}
if(ma==cc)
jum++;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
{
if(b[v[aa][ii]])continue;
if(v[aa][ii]==bb)continue;
dfs1(v[aa][ii],aa,cc+1);
}
}
void dfs2(ll aa,ll bb)
{
//cout<<isi[i][j]<<" "<<aa<<" "<<cc<<"_\n";
ll ii;
vector<pair<ll,ll> > tim;
zy[aa]=1;
for(ii=0;ii<v[aa].size();ii++)
{
if(b[v[aa][ii]])continue;
if(v[aa][ii]==bb)continue;
dfs2(v[aa][ii],aa);
if(zx[aa]<zx[v[aa][ii]])
{
zx[aa]=max(zx[aa],zx[v[aa][ii]]);
zy[aa]=0;
}
if(zx[aa]==zx[v[aa][ii]])
{
zy[aa]+=zy[v[aa][ii]];
}
tim.pb(za[v[aa][ii]]);
}
zx[aa]++;
sort(tim.begin(),tim.end());
reverse(tim.begin(),tim.end());
ll TS=tim.size();
if(TS<=1)
{
if(ma<zx[aa])
{
ma=max(ma,zx[aa]);
jum=0;
}
if(ma==zx[aa])
jum++;
za[aa]=mp(zx[aa],1);
za[aa].se=zy[aa];
//return ;
}
else
{
ll moa=tim[0].fi+tim[1].fi,bww;
// cout<<aa<<" "<<moa<<"___\n";
if(tim[0].fi==tim[1].fi)
{
ll ii,bw=0,bon=0;
for(ii=0;ii<tim.size();ii++)
{
if(tim[ii].fi<tim[0].fi)
{
break;
}
//cout<<aa<<"_\n";
bon+=bw*tim[ii].se;
bw+=tim[ii].se;
//cout<<aa<<" "<<bon<<" "<<bw<<"@\n";
}
bww=bw;
za[aa]=mp(moa,bon);
}
else
{
// cout<<aa<<"__\n";
ll ii,bw=0,bon=0;
for(ii=1;ii<tim.size();ii++)
{
if(tim[ii].fi<tim[1].fi)
{
break;
}
//cout<<aa<<"___\n";
bon+=tim[0].se*tim[ii].se;
}
za[aa]=mp(moa,bon);
bww=bw;
}
if(ma<moa)
{
ma=max(ma,moa);
jum=0;
}
if(ma==moa)
jum+=bww;
za[aa].se=zy[aa];
}
//cout<<aa<<" "<<za[aa].fi<<" "<<za[aa].se<<"__\n";
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff,ll gg)
{
if(aa==bb)
{
ST[ff][ee]=dd;
byk[ff][ee]=gg;
}
else
{
ll ce=(aa+bb)/2;
if(cc<=ce)
upd(aa,ce,cc,dd,ee*2,ff,gg);
else
upd(ce+1,bb,cc,dd,ee*2+1,ff,gg);
ST[ff][ee]=max(ST[ff][ee*2],ST[ff][ee*2+1]);
byk[ff][ee]=0;
if(ST[ff][ee]==ST[ff][ee*2])byk[ff][ee]+=byk[ff][ee*2];
if(ST[ff][ee]==ST[ff][ee*2+1])byk[ff][ee]+=byk[ff][ee*2+1];
}
//cout<<ff<<" "<<aa<<" "<<bb<<" "<<ee<<" "<<ST[ff][ee]<<" "<<byk[ff][ee]<<"\n";
}
void cari(ll aa,ll bb,ll cc,ll dd,ll ee)
{
if(bb<cc||dd<aa)return ;
else
if(cc<=aa&&bb<=dd)
tom.pb(ee);
else
{
ll ce=(aa+bb)/2;
cari(aa,ce,cc,dd,ee*2);
cari(ce+1,bb,cc,dd,ee*2+1);
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>ta>>tb;
v[ta].pb(tb);
v[tb].pb(ta);
}
dfs(1);
CS=cyc.size();
memset(b,0,sizeof(b));
for(i=0;i<CS;i++)b[cyc[i]]=1;
for(i=0;i<CS;i++)
{
ma=-1;
jum=0;
dfs1(cyc[i],cyc[i],0);
A[i]=mp(ma,jum);
//cout<<cyc[i]<<" "<<A[i].fi<<" "<<A[i].se<<"\n";
}
ma=-1;
jum=0;
for(i=0;i<CS;i++)
{
b[cyc[i]]=0;
dfs2(cyc[i],cyc[i]);
b[cyc[i]]=1;
}
//cout<<ma<<" ) "<<jum<<"\n";
jum*=2;
//jum=0;
K=CS*2-1;
for(i=0;i<CS*2;i++)
{
upd(0,K,i,i+A[i%CS].fi,1,0,A[i%CS].se);
upd(0,K,i,(K-i)+A[i%CS].fi,1,1,A[i%CS].se);
}
for(i=0;i<CS;i++)
{
ll L,R,C;
L=i+1;R=i+(CS)/2;C=A[i].fi;
while(L>=CS)
{
L-=CS;
R-=CS;
}
C-=(L-1);
tom.clear();cari(0,K,L,R,1);
// cout<<cyc[i]<<" "<<L<<" "<<R<<" "<<C<<"\n";
for(j=0;j<tom.size();j++)
{
// cout<<cyc[i]<<" "<<ST[0][tom[j]]+C<<"@\n";
if(ma<(ST[0][tom[j]]+C))
{
ma=(ST[0][tom[j]]+C);
jum=0;
}
if(ma==(ST[0][tom[j]]+C))
{
jum+=A[i].se*byk[0][tom[j]];
// cout<<cyc[i]<<" "<<ma<<" "<<jum<<"_\n";
}
}
L=(i-(CS)/2);R=i-1;C=A[i].fi;
while(L<0)
{
L+=CS;
R+=CS;
}
C+=(R+1)-K;
// cout<<cyc[i]<<" "<<L<<" "<<R<<" "<<C<<"__\n";
tom.clear();cari(0,K,L,R,1);
for(j=0;j<tom.size();j++)
{
// cout<<ST[1][tom[j]]+C<<"@\n";
if(ma<(ST[1][tom[j]]+C))
{
ma=(ST[1][tom[j]]+C);
jum=0;
}
if(ma==(ST[1][tom[j]]+C))
{
jum+=A[i].se*byk[1][tom[j]];
// cout<<cyc[i]<<" "<<ma<<" "<<jum<<"\n";
}
}
}
// for(i=0;i<CS;i++)
// {
// ll tam=1;
// for(j=i+1;j<=(i+(CS)/2);j++)
// {
// if(ma<(tam+A[i].fi+A[j%CS].fi))
// {
// ma=(tam+A[i].fi+A[j%CS].fi);
// jum=0;
// }
// if(ma==(tam+A[i].fi+A[j%CS].fi))
// {
// // cout<<cyc[i]<<" "<<cyc[j%CS]<<" "<<(tam+A[i].fi+A[j%CS].fi)<<"\n";
// jum+=A[i].se*A[j%CS].se;
// }
// tam++;
// }
// tam=1;
// for(j=i-1;j>=(i-(CS)/2);j--)
// {
// if(ma<(tam+A[i].fi+A[(j+CS)%CS].fi))
// {
// ma=(tam+A[i].fi+A[(j+CS)%CS].fi);
// jum=0;
// }
// if(ma==(tam+A[i].fi+A[(j+CS)%CS].fi))
// {
// // cout<<cyc[i]<<" "<<cyc[(j+CS)%CS]<<" "<<ma<<"\n";
// jum+=A[i].se*A[(j+CS)%CS].se;
// }
// tam++;
// }
// }
//cout<<ma<<" "<<jum<<"\n";
jum/=2;
cout<<jum<<"\n";
}
Compilation message
shymbulak.cpp: In function 'void dfs(ll)':
shymbulak.cpp:19:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(ll, ll, ll)':
shymbulak.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(ll, ll)':
shymbulak.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
shymbulak.cpp:104:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<tim.size();ii++)
~~^~~~~~~~~~~
shymbulak.cpp:122:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=1;ii<tim.size();ii++)
~~^~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:230:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<tom.size();j++)
~^~~~~~~~~~~
shymbulak.cpp:253:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<tom.size();j++)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11384 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11384 KB |
Output is correct |
| 3 |
Correct |
14 ms |
11384 KB |
Output is correct |
| 4 |
Correct |
12 ms |
11384 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
11512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
11772 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
11508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
20720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
