#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=2e5+5;
int n,x,y,vis[maxn],par[maxn],now,sz,L[4*maxn],pos,apos;
ll jog[maxn],ans,pat[maxn];
pair<int,int>dp[maxn],T[4*maxn],nw;
vector<int>E[maxn],v;
void dfs(int nd,int pr){
par[nd] = pr;
vis[nd] = 1;
for(auto i : E[nd]){
if(vis[i] == 1 and i != pr and (int)v.size() == 0){
now = nd; while(now != i) v.push_back(now),now=par[now]; v.push_back(i);
continue;
}
if(i != pr and vis[i] != 1) dfs(i,nd);
}
return;
}
void dfs1(int nd,int pr){
pair<int,int> a = {-1,-1},b = {-1,-1};
dp[nd] = {0,1};
for(auto i : E[nd]){
if(i != pr and vis[i] == 0){
dfs1(i,nd);
if(dp[i].first > a.first) b=a,a=dp[i];
else if(dp[i].first > b.first) b=dp[i];
}
}
if(a == make_pair(-1,-1) and b == make_pair(-1,-1)) return;
pat[a.first+1] += a.second;
if(a != make_pair(-1,-1) and b != make_pair(-1,-1)) pat[a.first+b.first+2] += 1ll*a.second*b.second;
if(a.first == b.first) dp[nd] = {a.first+1,a.second+b.second};
else if(a.first > b.first) dp[nd] = {a.first+1,a.second};
else dp[nd] = {b.first+1,b.second};
}
void prop(int nd){
T[nd*2].first += L[nd];
L[nd*2] += L[nd];
T[nd*2+1].first += L[nd];
L[nd*2+1] += L[nd];
L[nd] = 0;
}
void f(int nd){
if(T[nd*2].first == T[nd*2+1].first) T[nd] = {T[nd*2].first,T[nd*2].second+T[nd*2+1].second};
else if(T[nd*2].first > T[nd*2+1].first) T[nd] = T[nd*2];
else T[nd] = T[nd*2+1];
}
void upd(int pos,int val,int val1,int l,int r,int nd){
if(l == r){
T[nd].first=val,T[nd].second=val1;
return;
}
prop(nd);
if(pos <= (l+r)/2) upd(pos,val,val1,l,(l+r)/2,nd*2);
else upd(pos,val,val1,(l+r)/2+1,r,nd*2+1);
f(nd);
}
void lupd(int a,int b,int val,int l,int r,int nd){
if(r < a or l > b) return;
if(l >= a and r <= b){
T[nd].first += val;
L[nd] += val;
return;
}
prop(nd);
lupd(a,b,val,l,(l+r)/2,nd*2);
lupd(a,b,val,(l+r)/2+1,r,nd*2+1);
f(nd);
}
pair<int,int>tap(int a,int b,int l,int r,int nd){
if(r < a or l > b) return {0,0};
if(l >= a and r <= b) return T[nd];
prop(nd);
pair<int,int>cep=tap(a,b,l,(l+r)/2,nd*2);
pair<int,int>sag=tap(a,b,(l+r)/2+1,r,nd*2+1);
if(cep.first == sag.first) return {cep.first,cep.second+sag.second};
if(cep.first > sag.first) return cep;
return sag;
}
int dis(int a,int b){
if(b < a) swap(a,b);
return min(b-a,a+sz-b);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++){
cin >> x >> y;
E[x].push_back(y);
E[y].push_back(x);
}
dfs(1,0);
memset(vis,0,sizeof(vis));
for(auto i : v) vis[i] = 1;
for(auto i : v) dfs1(i,0);
// for(auto i : v) cout<<i<<' ';
sz = v.size();
upd(0,dp[v[0]].first,dp[v[0]].second,0,sz-1,1);
for(int i = 1;i < sz;i++){
upd(i,dp[v[i]].first+dis(0,i),dp[v[i]].second,0,sz-1,1);
if(dis(1,i) < dis(0,i)) pos=i;
if(dis(1,i) == dis(0,i)-1) apos=i;
}
if(sz % 2 == 1) apos=-1;
// cout<<apos<<'\n';
nw = tap(1,sz-1,0,sz-1,1);
// cout<<"0 "<<v[0]<<' '<<nw.first<<' '<<nw.second<<' '<<apos<<'\n';
jog[nw.first+dp[v[0]].first] += 1ll*nw.second*dp[v[0]].second;
if(apos != -1 and dis(0,apos)+dp[v[apos]].first == nw.first) jog[nw.first+dp[v[0]].first] += 1ll*dp[v[apos]].second*dp[v[0]].second;
if(apos != -1) apos++;
for(int i = 1;i < sz-1;i++){
if(pos == sz) pos = 0;
if(apos == sz) apos = 0;
if(pos < i){
lupd(i,sz-1,-1,0,sz-1,1);
lupd(0,pos,-1,0,sz-1,1);
now = pos+1;
if(dis(now,i) == dis(now,i-1)) now++;
lupd(now,i-1,1,0,sz-1,1);
}
else {
lupd(i,pos,-1,0,sz-1,1);
if(dis(0,i) > dis(0,i-1)) lupd(0,i-1,1,0,sz-1,1);
else if(dis(0,i) == dis(0,i-1)) lupd(1,i-1,1,0,sz-1,1);
now = pos+1;
if(now < sz and dis(i,now) == dis(i-1,now)) now++;
if(now < sz) lupd(now,sz-1,1,0,sz-1,1);
}
nw = tap(i+1,sz-1,0,sz-1,1);
// cout<< i <<' '<< v[i] << ' '<< nw.first << ' ' << nw.second<<' '<<v[apos]<<'\n';
jog[nw.first+dp[v[i]].first] += 1ll*nw.second*dp[v[i]].second;
if(apos != -1 and dis(i,apos)+dp[v[apos]].first == nw.first) jog[nw.first+dp[v[i]].first] += 1ll*dp[v[apos]].second*dp[v[i]].second;
if(apos != -1) apos++;
pos++;
}
for(int i = 0;i <= n;i++){
// cout<<i<<' '<<jog[i]<<'\n';
if(pat[i] > 0 or jog[i] > 0) ans = pat[i]+jog[i];
}
cout<<ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5868 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5996 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
73 ms |
11052 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
11492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
