#include <stdio.h>
#include <vector>
#include <deque>
#define N_MAX 200000
using namespace std;
struct path {
int dist;
long long cnt;
} Depth[N_MAX+1], Ans;
vector <int> Road[N_MAX+1];
deque <path> Deq;
int N, C, K, Cycle[N_MAX+2], Check[N_MAX+1];
int findCycle(int now, int prev) {
int i, j=Road[now].size(), isCycle=0;
Check[now]=1;
for(i=0 ; i<j ; i++) {
if(Check[Road[now][i]]) {
if(Road[now][i]!=prev) {
isCycle=Road[now][i];
break;
}
}
else {
isCycle=findCycle(Road[now][i],now);
if(isCycle)
break;
}
}
Check[now]=0;
if(isCycle>0) {
Cycle[++C]=now;
if(now==isCycle)
return -1;
}
return isCycle;
}
path getDepth(int now) {
int i, j=Road[now].size(), max2=0;
long long sum=0, num1, num2=1;
path x, max1={0,1};
vector <long long> cnt;
Check[now]=1;
cnt.push_back(1);
for(i=0 ; i<j ; i++)
if(!Check[Road[now][i]]) {
x=getDepth(Road[now][i]);
if(max1.dist<x.dist) {
max2=max1.dist;
max1=x;
}
else if(max2<x.dist) {
max2=x.dist;
cnt.clear();
cnt.push_back(x.cnt);
}
else if(max2==x.dist)
cnt.push_back(x.cnt);
}
Check[now]=0;
j=cnt.size();
for(i=0 ; i<j ; i++)
sum+=cnt[i];
num1=max1.cnt*sum;
if(max1.dist)
num2=max1.cnt;
if(max1.dist==max2)
for(i=0 ; i<j ; i++) {
sum-=cnt[i];
num1+=cnt[i]*sum;
if(max2)
num2+=cnt[i];
}
if(Ans.dist<max1.dist+max2)
Ans={max1.dist+max2+1,num1};
else if(Ans.dist==max1.dist+max2+1)
Ans.cnt+=num1;
return {max1.dist+1,num2};
}
int main(void) {
int i, x, y, prev;
scanf("%d",&N);
for(i=1 ; i<=N ; i++) {
scanf("%d %d",&x,&y);
Road[x].push_back(y);
Road[y].push_back(x);
}
findCycle(1,0);
Cycle[0] =Cycle[C];
Cycle[C+1]=Cycle[1];
for(i=1 ; i<=C ; i++) {
Check[Cycle[i-1]]=Check[Cycle[i+1]]=1;
Check[Cycle[i]]=0;
Depth[i]=getDepth(Cycle[i]);
}
K=C/2;
for(i=C-K+1 ; i<=C ; i++) {
while(!Deq.empty() && Deq.back().dist<Depth[i].dist+C-i+1)
Deq.pop_back();
if(!Deq.empty() && Deq.back().dist==Depth[i].dist+C-i+1)
Deq.back().cnt+=Depth[i].cnt;
else
Deq.push_back({Depth[i].dist+C-i+1,Depth[i].cnt});
}
for(i=1 ; i<=C ; i++) {
x=Deq.front().dist+Depth[i].dist+i-2;
y=Deq.front().cnt*Depth[i].cnt;
if(Ans.dist<x)
Ans={x,y};
else if(Ans.dist==x)
Ans.cnt+=y;
prev=i-K;
if(prev<=0)
prev+=C;
if(Deq.front().dist+i-K-1==Depth[prev].dist) {
Deq.front().cnt-=Depth[prev].cnt;
if(!Deq.front().cnt)
Deq.pop_front();
}
while(!Deq.empty() && Deq.back().dist<Depth[i].dist-i+1)
Deq.pop_back();
if(!Deq.empty() && Deq.back().dist==Depth[i].dist-i+1)
Deq.back().cnt+=Depth[i].cnt;
else
Deq.push_back({Depth[i].dist-i+1,Depth[i].cnt});
}
Deq.clear();
for(i=K ; i>=1 ; i--) {
while(!Deq.empty() && Deq.back().dist<Depth[i].dist+i)
Deq.pop_back();
if(!Deq.empty() && Deq.back().dist==Depth[i].dist+C+i)
Deq.back().cnt+=Depth[i].cnt;
else
Deq.push_back({Depth[i].dist+i,Depth[i].cnt});
}
for(i=C ; i>=1 ; i--) {
x=Deq.front().dist+Depth[i].dist+C-i-1;
y=Deq.front().cnt*Depth[i].cnt;
if(Ans.dist<x)
Ans={x,y};
else if(Ans.dist==x)
Ans.cnt+=y;
prev=i+K;
if(prev>C)
prev-=C;
if(Deq.front().dist+C-i-K==Depth[prev].dist) {
Deq.front().cnt-=Depth[prev].cnt;
if(!Deq.front().cnt)
Deq.pop_front();
}
while(!Deq.empty() && Deq.back().dist<Depth[i].dist+i-C)
Deq.pop_back();
if(!Deq.empty() && Deq.back().dist==Depth[i].dist+i-C)
Deq.back().cnt+=Depth[i].cnt;
else
Deq.push_back({Depth[i].dist+i-C,Depth[i].cnt});
}
printf("%lld",Ans.cnt/2);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
10960 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 4 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
10960 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
10960 KB |
Output isn't correct |
| 7 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 8 |
Correct |
2 ms |
10960 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
10960 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
10960 KB |
Output isn't correct |
| 11 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 12 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
10960 KB |
Output isn't correct |
| 14 |
Correct |
2 ms |
10960 KB |
Output is correct |
| 15 |
Correct |
0 ms |
10960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
10960 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 4 |
Correct |
0 ms |
10960 KB |
Output is correct |
| 5 |
Correct |
0 ms |
11092 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
11276 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
11092 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
11092 KB |
Output isn't correct |
| 9 |
Correct |
0 ms |
11092 KB |
Output is correct |
| 10 |
Correct |
0 ms |
11092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
13864 KB |
Output isn't correct |
| 2 |
Incorrect |
62 ms |
14260 KB |
Output isn't correct |
| 3 |
Correct |
48 ms |
17380 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
14128 KB |
Output isn't correct |
| 5 |
Correct |
43 ms |
14128 KB |
Output is correct |
| 6 |
Incorrect |
135 ms |
16504 KB |
Output isn't correct |
| 7 |
Incorrect |
96 ms |
15580 KB |
Output isn't correct |
| 8 |
Incorrect |
82 ms |
17296 KB |
Output isn't correct |
| 9 |
Correct |
127 ms |
17296 KB |
Output is correct |
| 10 |
Correct |
94 ms |
17744 KB |
Output is correct |
| 11 |
Incorrect |
110 ms |
21004 KB |
Output isn't correct |
| 12 |
Incorrect |
115 ms |
21316 KB |
Output isn't correct |
