| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 13157 | 2015-02-01T09:35:24 Z | woqja125 | 관광지 (IZhO14_shymbulak) | C++ | 0 ms | 0 KB |
#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;
inline int cn(int x){return dist[cycles[(x)%CC]];}
inline int cd(int x){return distC[cycles[(x)%CC]];}
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;
}
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)
{
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);
int max;
long long C;
max = C = 0;
int Allmax;
long long AllC;
int j;
for(j=1; j-i<=CC-j; j++)
{
if(cn(j)+j > max)
{
max = cn(j)+j;
C = cd(j);
}
else if(cn(j)+j == max) C+=cd(j);
}
Allmax = max + cn(0);
AllC = 1ll*C*cd(0);
for(i=1; i<CC; i++)
{
max --;
if(cn(j)+j-i > max)
{
max = cn(j)+j-i;
C = cd(j);
}
else if(cn(j)+j-i == max) C+=cd(j);
if(max + cn(i) > Allmax)
{
Allmax = max+cn(i);
AllC = 1ll*cd(i)*C;
}
else if(max +cn(i) == Allmax)
{
AllC += 1ll*cd(i)*C;
}
j++;
}
printf("%lld", AllC);
return 0;
}