#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> adj[N];
bool on_cycle[N];
int par[N];
int vis[N];
int dep[N];
pair<int,int> maxi[N];
vector<int> cycle;
pair<int,long long> merge(pair<int,long long> a,pair<int,long long> b){
pair<int,long long> ret = {0,0};
ret.first = max(a.first,b.first);
if(a.first == ret.first)ret.second += a.second;
if(b.first == ret.first)ret.second += b.second;
return ret;
}
pair<int,long long> merge2(pair<int,long long> a,pair<int,long long> b){
return {a.first + b.first,a.second*b.second};
}
struct SegTree{
vector<pair<int,long long>> t;
int n;
SegTree(int size){
n = size;
t.assign(4*n,{-1e9,0});
}
void upd(int v,int tl,int tr,int pos,pair<int,long long> val){
if(tl == tr){
t[v] = merge(t[v],val);
return;
}
int tm = (tl + tr)/2;
if(pos <= tm)
upd(v*2,tl,tm,pos,val);
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = merge(t[v*2],t[v*2+1]);
}
pair<int,long long> get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return {-1e9,0};
if(l <= tl && tr <= r)
return t[v];
int tm = (tl + tr)/2;
return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int pos,pair<int,long long> val){
upd(1,0,n,pos,val);
}
pair<int,long long> get(int l,int r){
return get(1,0,n,l,r);
}
};
void dfs(int v,int pr){
vis[v] = 1;
par[v] = pr;
for(auto u:adj[v]){
if(u == pr)continue;
if(cycle.size())return;
if(vis[u] == 1){
while(1){
on_cycle[v] = 1;
cycle.push_back(v);
if(u == v)break;
v = par[v];
}
}
if(cycle.size())return;
dfs(u,v);
}
vis[v] = 2;
}
pair<int,long long> res;
void dfs1(int v,int pr){
maxi[v] = {dep[v],1};
for(auto u:adj[v]){
if(u == pr || on_cycle[u])continue;
dep[u] = dep[v] + 1;
dfs1(u,v);
res = merge(res,{maxi[v].first + maxi[u].first - 2*dep[v],2*maxi[v].second * maxi[u].second});
maxi[v] = merge(maxi[v],maxi[u]);
}
res = merge(res,{maxi[v].first-dep[v],maxi[v].second});
}
pair<int,long long> get_diameter_and_count(int v){
res = {0,0};
dfs1(v,0);
return res;
}
void solve(){
int n;
cin >> n;
for(int i = 1;i<=n;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,0);
assert(cycle.size() >= 3);
// for(auto u:cycle){
// cout << u << " ";
// }
// cout << endl;
pair<int,long long> ans = {0,0};
for(auto u:cycle){
ans = merge(ans,get_diameter_and_count(u));
}
/*
int sz = cycle.size();
for(int i = 0;i<sz;i++){
for(int j = 0;j<sz;j++){
if(i == j)continue;
//cout << cycle[i] << " " << cycle[j] << " " << maxi[cycle[i]].first + maxi[cycle[j]].first + min(abs(i-j),sz-abs(i-j)) << endl;
ans = merge(ans,{maxi[cycle[i]].first + maxi[cycle[j]].first + min(abs(i-j),sz-abs(i-j)),maxi[cycle[i]].second * maxi[cycle[j]].second});
if(abs(i-j) == sz - abs(i-j))
ans = merge(ans,{maxi[cycle[i]].first + maxi[cycle[j]].first + min(abs(i-j),sz-abs(i-j)),maxi[cycle[i]].second * maxi[cycle[j]].second});
}
}*/
if(cycle.size() % 2){
int half_sz = cycle.size()/2;
int sz = cycle.size();
SegTree t(2*sz);
SegTree t2(2*sz);
for(int i = 0;i<2*sz;i++){
t.upd(i,{maxi[cycle[i%sz]].first + i,maxi[cycle[i%sz]].second});
}
for(int i = 0;i<2*sz;i++){
t2.upd(i,{maxi[cycle[i%sz]].first - i,maxi[cycle[i%sz]].second});
}
for(int i = 0;i<sz;i++){
pair<int,long long> nowl = t2.get(i + half_sz + 1,i + sz-1);
nowl.first += i + sz;
pair<int,long long> nowr = t.get(i+1,i+half_sz);
nowr.first -= i;
nowl = merge2(nowl,maxi[cycle[i]]);
nowr = merge2(nowr,maxi[cycle[i]]);
ans = merge(ans,nowl);
ans = merge(ans,nowr);
}
}
else{
int half_sz = cycle.size()/2 - 1;
int sz = cycle.size();
SegTree t(2*sz);
SegTree t2(2*sz);
for(int i = 0;i<2*sz;i++){
t.upd(i,{maxi[cycle[i%sz]].first + i,maxi[cycle[i%sz]].second});
}
for(int i = 0;i<2*sz;i++){
t2.upd(i,{maxi[cycle[i%sz]].first - i,maxi[cycle[i%sz]].second});
}
for(int i = 0;i<sz;i++){
pair<int,long long> nowl = t2.get(i + half_sz + 2,i + sz-1);
nowl.first += i + sz;
pair<int,long long> nowr = t.get(i+1,i+half_sz);
nowr.first -= i;
pair<int,long long> middle = {half_sz + 1 + maxi[cycle[(i+half_sz+1)%sz]].first,2*maxi[cycle[(i+half_sz+1)%sz]].second};
nowl = merge2(nowl,maxi[cycle[i]]);
nowr = merge2(nowr,maxi[cycle[i]]);
middle = merge2(middle,maxi[cycle[i]]);
ans = merge(ans,nowl);
ans = merge(ans,nowr);
ans = merge(ans,middle);
}
}
cout << ans.second / 2 << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4944 KB |
Output is correct |
| 13 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 15 |
Correct |
3 ms |
5076 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5204 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5196 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
41 ms |
9724 KB |
Output is correct |
| 2 |
Correct |
39 ms |
10316 KB |
Output is correct |
| 3 |
Correct |
77 ms |
26952 KB |
Output is correct |
| 4 |
Correct |
44 ms |
11536 KB |
Output is correct |
| 5 |
Correct |
44 ms |
11420 KB |
Output is correct |
| 6 |
Incorrect |
104 ms |
16440 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
