#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[101010],b[101010],CS,ma,jum,has,j,K;
vector<ll> v[101010],cyc,isi[101010],tom;
pair<ll,ll> A[101010];
ll ST[2][1601601];
ll byk[2][1601601];
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,ll cc)
{
//cout<<isi[i][j]<<" "<<aa<<" "<<cc<<"_\n";
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;
dfs2(v[aa][ii],aa,cc+1);
}
}
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;
for(j=0;j<isi[i].size();j++)
{
//cout<<isi[i][j]<<"\n";
dfs2(isi[i][j],isi[i][j],0);
}
b[cyc[i]]=1;
}
//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);
}
jum/=2;
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;
}
else
{
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;
}
else
{
// 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:17: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:49: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, ll)':
shymbulak.cpp:67:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:135:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<isi[i].size();j++)
~^~~~~~~~~~~~~~
shymbulak.cpp:162:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<tom.size();j++)
~^~~~~~~~~~~
shymbulak.cpp:185: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 |
7 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1558 ms |
11892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
