#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 200005;
const int inf = 1e9 + 5;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
int n;
vector<int> g[maxn];
vector<int> krug;
int par[maxn];
int visited[maxn];
void dfs1(int v, int p){
par[v] = p;
visited[v] = 1;
for(auto u : g[v]){
if(u == p)continue;
if(!visited[u])dfs1(u, v);
else{
if(visited[u] == 1){
int a = v;
while(a != u){
krug.pb(a);
a = par[a];
}
krug.pb(u);
}
}
}
visited[v] = 2;
}
pii kol[maxn];
bool bio[maxn];
int mx = 0;
int br = 0;
bool was[maxn];
void dfs2(int v, int duz){
if(duz > mx){
mx = duz;
br = 0;
}
if(mx == duz)br += 1;
was[v] = 1;
for(auto u : g[v]){
if(!was[u])dfs2(u, duz + 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
cin >> n;
ff(i,1,n){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs1(1, -1);
for(auto c : krug)was[c] = 1;
ff(i,0,sz(krug) - 1){
mx = 0;
br = 0;
dfs2(krug[i], 0);
kol[krug[i]] = {mx, br};
}
int len = sz(krug);
int mxdist = len / 2;
int j = 0;
while(j < len)krug.pb(krug[j++]);
multiset<int> ms;
ff(i,0,mxdist - 1){
int x = kol[krug[i]].se;
while(x--)ms.insert(i - kol[krug[i]].fi);
}
int najv = 0;
int ima = 0;
ff(i,mxdist,sz(krug) - 1){
if(bio[krug[i]])break;
bio[krug[i]] = 1;
if(kol[krug[i]].fi + i - *ms.begin() > najv){
najv = kol[krug[i]].fi + i - *ms.begin();
ima = 0;
}
if(kol[krug[i]].fi + i - *ms.begin() == najv)ima += kol[krug[i]].se * ms.count(*ms.begin());
{
int x = kol[krug[i - mxdist]].se;
while(x--)ms.erase(ms.find(i - mxdist - kol[krug[i - mxdist]].fi));
}
{
int x = kol[krug[i]].se;
while(x--)ms.insert(i - kol[krug[i]].fi);
}
}
cout << ima << endl;
return 0;
}
/**
6
1 2
1 3
2 4
4 3
4 5
4 6
8
1 2
1 3
1 7
7 8
2 4
4 3
4 5
4 6
// probati bojenje sahovski ili slicno
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
5100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
