#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ft first
#define sd second
const ll MOD = 1e9+7;
ll n, used[200005], ver[200005], z[1000010], ti = 1;
vector<ll>g[200005], cic;
pair<ll, ll>t[1000010], arr[200005];
set<ll>s;
map<ll, ll>mp;
void dfs(ll v = 1, ll p = -1){
used[v] = 1;
for(auto to : g[v]){
if(used[to] == 1 && to != p){
used[to] = 3;
used[v] = 2;
}
else if(used[to] == 0){
dfs(to, v);
if(used[to] == 2 && used[v] != 3){
used[v] = 2;
}
}
}
if(used[v] == 3 || used[v] == 2)
cic.push_back(v), ver[v] = ti++;
}
pair<ll, ll> dfs1(ll v, ll p = -1){
pair<ll, ll>mxx = {0, 0}, mmxx = {0, 0};
ll mx = 0, c = 1;
for(auto to : g[v]){
if(to != p && used[to] == 1){
auto xx = dfs1(to, v);
if(xx.ft > mx)
mx = xx.ft, c = xx.sd;
else if(xx.ft == mx)
c += xx.sd;
if(mx > mxx.ft || (mx == mxx.ft && c > mxx.sd)){
mmxx = mxx;
mxx = {mx, c};
}
else if(mx > mmxx.ft || (mx == mmxx.ft && c > mmxx.sd))
mmxx = {mx, c};
}
}
s.insert(mxx.ft + mmxx.ft);
mp[mxx.ft + mmxx.ft] += mxx.sd * mmxx.sd / 2;
return {mx + 1, c};
}
pair<ll, ll> combine(pair<ll, ll>l, pair<ll, ll>r){
if(l.ft > r.ft)
return l;
else if(r.ft > l.ft)
return r;
else
return {l.ft, l.sd + r.sd};
}
void build(ll v = 1, ll tl = 1, ll tr = n){
if(tl == tr)
t[v] = arr[tl];
else{
ll tm = (tl + tr) / 2;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
t[v] = combine(t[v + v], t[v + v + 1]);
}
}
void prp(ll v){
t[v].ft += z[v];
if(v + v <= 8e5){
z[v + v] += z[v];
z[v + v + 1] += z[v];
}
z[v] = 0;
}
pair<ll, ll> get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n){
prp(v);
if(tl > r || tr < l)
return {0, 0};
if(l <= tl && tr <= r)
return t[v];
ll tm = (tl + tr) / 2;
return combine(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
void upd(ll l, ll r, ll val, ll v = 1, ll tl = 1, ll tr = n){
prp(v);
if(tl > r || tr < l)
return;
if(l <= tl && tr <= r){
z[v] += val;
prp(v);
return;
}
ll tm = (tl + tr) / 2;
upd(l, r, val, v + v, tl, tm);
upd(l, r, val, v + v + 1, tm + 1, tr);
}
void upd1(ll pos, bool mode, ll v = 1 , ll tl = 1, ll tr = n){
if(tl == tr){
if(mode)
t[v].sd <<= 1;
else
t[v].sd >>= 1;
return;
}
ll tm = (tl + tr) / 2;
if(tm <= pos)
upd1(pos, mode, v + v, tl, tm);
else
upd1(pos, mode, v + v + 1, tm + 1, tr);
}
void fun(){
cin>>n;
for(ll i = 1, a, b; i <= n; i++){
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs();
for(auto it : cic)
arr[ver[it]] = dfs1(it), arr[ver[it]].ft--;
n = cic.size();
for(ll i = 2; i <= n; i++)arr[i].ft += min(i - 1, n - i + 1);
build();
for(ll i = 1; i <= n; i++){
ll xxx = ((i + (n / 2) - 1 + n) % n) + 1;
if(i > 1){
if(i + (n / 2) - 1 > n)
upd(i, n, -1), upd(1, i + (n / 2) - 1 - n, -1);
else
upd(i, i + (n / 2) - 1, -1);
ll xx = (((i - n / 2) - 1 + n) % n) + 1;
if(xx + (n / 2) - 1 > n)
upd(xx, n, 1), upd(1, xx + (n / 2) - 1 - n, 1);
else
upd(xx, xx + (n / 2) - 1, 1);
if(n % 2 == 0)upd1(xxx, 1);
}
pair<ll, ll> x;
if(i == 1)
x = get(2, n);
else if(i < n)
x = combine(get(1, i - 1), get(i + 1, n));
else
x = get(1, n - 1);
s.insert(x.ft);
mp[x.ft] += x.sd * arr[i].sd;
if(i > 1 && n % 2 == 0)
upd1(xxx, 0);
}
auto it = s.end();it--;
cout<<mp[*it]<<endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int ttt = 1;
//cin>>ttt;
while(ttt--)fun();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5004 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
9804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
