#include<stdio.h>
#include<vector>
#include<queue>
std::vector<int> map[200001];
int deg[200001];
int n;
int dist[200001], distC[200001];
int v[200001];
int cycles[200001], CC = 0;
long long solve(int , long long);
int main()
{
int i, x, xx;
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%d%d", &x, &xx);
map[x].push_back(xx);
map[xx].push_back(x);
deg[x]++;
deg[xx]++;
}
std::queue<int> Q;
for(i=1; i<=n; i++)
{
if(deg[i] == 1)Q.push(i);
distC[i] = 1;
}
int max = 0;
long long maxC = 0;
while(!Q.empty())
{
x = Q.front();
Q.pop();
v[x] = true;
for(int t :map[x]) if(v[t] == false){ xx=t; break; }
deg[xx]--;
if(deg[xx] == 1) Q.push(xx);
if(dist[xx] + dist[x] + 1 > max)
{
max = dist[xx] + dist[x] + 1;
maxC = 1ll * distC[xx] * distC[x];
}
else if(dist[xx] + dist[x] + 1 == max)
{
maxC += 1ll*distC[xx]*dist[x];
}
if(dist[xx] < dist[x]+1)
{
dist[xx] = dist[x]+1;
distC[xx] = distC[x];
}
else if(dist[xx] == dist[x] + 1) distC[xx]+=distC[x];
}
for(i=1; i<=n; i++) if(deg[i] != 1) break;
xx = x = i;
do
{
v[xx] = true;
cycles[CC++] = xx;
int tx=-1;
for(int t: map[xx]) if(!v[t]){ tx = t; break;}
xx = tx;
}while(xx!=-1);
printf("%lld", solve(max, maxC));
return 0;
}
int im[1050000];
long long imc[1050000];
int b;
inline int cn(int x){return dist[cycles[(x)%CC]];}
inline int cd(int x){return distC[cycles[(x)%CC]];}
void add(int &m, long long &mC, int m1, long long mc1, int m2, long long mc2)
{
if(m1 == m2)
{
m = m1;
mC = mc1 + mc2;
}
else if(m1 > m2)
{
m = m1;
mC = mc1;
}
else
{
m = m2;
mC = mc2;
}
}
void get(int &rm, long long &rmc, int f, int r)
{
f+=b; r+=b;
rm = rmc = 0;
while(f<r)
{
if(f%2 == 1) { add(rm, rmc, rm, rmc, im[f], imc[f]); f++; }
if(r%2 == 0) { add(rm, rmc, rm, rmc, im[r], imc[r]); r--; }
f/=2; r/=2;
}
if(f==r) add(rm, rmc, rm, rmc, im[f], imc[f]);
}
long long solve(int max, long long maxC)
{
int i;
for(b=1; b<=2*CC; b*=2);
for(i=0; i<2*CC; i++)
{
im[b+i] = cn(i) + i;
imc[b+i] = cd(i);
}
for(i=b-1; i>=1; i--) add(im[i], imc[i], im[i*2], imc[i*2], im[i*2+1], imc[i*2+1]);
int tm;
long long tmc;
int j;
for(j=0; j <= CC-j; j++);
for(i=0; i<CC; i++)
{
get(tm, tmc, i+1, j-1);
add(max, maxC, max, maxC, tm-i+cn(i), tmc*cd(i));
j++;
}
return maxC;
}
Compilation message
shymbulak.cpp: In function ‘int main()’:
shymbulak.cpp:36:14: error: range-based ‘for’ loops are not allowed in C++98 mode
for(int t :map[x]) if(v[t] == false){ xx=t; break; }
^
shymbulak.cpp:64:14: error: range-based ‘for’ loops are not allowed in C++98 mode
for(int t: map[xx]) if(!v[t]){ tx = t; break;}
^
shymbulak.cpp:14:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
shymbulak.cpp:17:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &xx);
^
