#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];
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){
dp[nd] = {0,1};
vector<pair<int,int>>res;
map<int,int>m,p;
for(auto i : E[nd]){
if(i != pr and vis[i] == 0){
dfs1(i,nd);
res.push_back(dp[i]);
m[dp[i].first] += dp[i].second;
p[dp[i].first]++;
}
}
if((int)res.size()==0) return;
jog[(*m.rbegin()).first+1] += (*m.rbegin()).second;
if(res.size() > 1){
sort(res.begin(),res.end());
if(p[res.back().first] > 1){
ll jg = 1;
for(int i = (int)res.size()-1;i >= 0;i--){
if(res[i].first != res.back().first) break;
jg *= res[i].second;
}
jog[res.back().first*2+2] += jg;
}
else {
auto t = m.rbegin(); t++;
jog[(*t).first+(*m.rbegin()).first+2] += 1ll * (*t).second * (*m.rbegin()).second;
}
}
dp[nd] = {(*m.rbegin()).first+1,(*m.rbegin()).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<<' '; cout<<'\n';
// cout<<dp[5].first<<' '<<dp[5].second<<'\n';
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<<v[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 and apos > i) jog[nw.first+dp[v[i]].first] += 1ll*dp[v[apos]].second*dp[v[i]].second;
if(apos != -1) apos++;
pos++;
// cout<<jog[3]<<'\n';
}
for(int i = n;i >= 1;i--) if(jog[i]) return cout<<jog[i],0;
}
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5996 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
9956 KB |
Output is correct |
| 2 |
Correct |
74 ms |
10340 KB |
Output is correct |
| 3 |
Correct |
125 ms |
16372 KB |
Output is correct |
| 4 |
Correct |
56 ms |
10212 KB |
Output is correct |
| 5 |
Correct |
58 ms |
10340 KB |
Output is correct |
| 6 |
Correct |
201 ms |
13668 KB |
Output is correct |
| 7 |
Correct |
136 ms |
13924 KB |
Output is correct |
| 8 |
Correct |
117 ms |
17124 KB |
Output is correct |
| 9 |
Correct |
114 ms |
17252 KB |
Output is correct |
| 10 |
Correct |
107 ms |
18148 KB |
Output is correct |
| 11 |
Incorrect |
119 ms |
19288 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
