#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,int c){
maxi[v] = {dep[v],1};
par[v] = c;
for(auto u:adj[v]){
if(u == pr || on_cycle[u])continue;
dep[u] = dep[v] + 1;
dfs1(u,v,c);
res = merge(res,{maxi[v].first + maxi[u].first - 2*dep[v],maxi[v].second * maxi[u].second});
maxi[v] = merge(maxi[v],maxi[u]);
}
}
pair<int,long long> get_diameter_and_count(int v,int x){
res = {0,0};
dfs1(v,0,x);
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);
for(int i = 0;i<cycle.size();i++){
get_diameter_and_count(cycle[i],i);
//cout << cycle[i] << " ";
}
//cout << endl;
int ans1 = 0,ans2 = 0;
for(int i = 1;i<=n;i++){
vector<int> d(n+1,-1);
queue<int> q;
q.push(i);
d[i] = 0;
while(q.size()){
auto tp = q.front();
q.pop();
for(auto u:adj[tp]){
if(d[u] == -1){
q.push(u);
d[u] = d[tp] + 1;
}
}
}
for(int j = 1;j<=n;j++){
if(d[j] > ans1){
ans1 = d[j];
ans2 = 0;
}
if(d[j] == ans1)ans2++;
if(d[j] == ans1 && (cycle.size()%2 == 0) && (par[j] == (par[i] + cycle.size()/2)%cycle.size()))ans2++;
}
}
cout << ans2/2;
}
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
}
Compilation message
shymbulak.cpp: In function 'void solve()':
shymbulak.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0;i<cycle.size();i++){
| ~^~~~~~~~~~~~~
shymbulak.cpp:127:65: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | if(d[j] == ans1 && (cycle.size()%2 == 0) && (par[j] == (par[i] + cycle.size()/2)%cycle.size()))ans2++;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
Correct |
3 ms |
5048 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 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 |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
7 ms |
5076 KB |
Output is correct |
| 15 |
Correct |
6 ms |
5092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
5144 KB |
Output is correct |
| 2 |
Correct |
11 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
21 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
20 ms |
5076 KB |
Output is correct |
| 5 |
Correct |
419 ms |
5304 KB |
Output is correct |
| 6 |
Correct |
322 ms |
5352 KB |
Output is correct |
| 7 |
Correct |
498 ms |
5312 KB |
Output is correct |
| 8 |
Correct |
477 ms |
5332 KB |
Output is correct |
| 9 |
Correct |
425 ms |
5332 KB |
Output is correct |
| 10 |
Correct |
500 ms |
5320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1582 ms |
10304 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
