#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];
int dia = 0;
int brdia = 0;
int dfs2(int v, int duz){
if(duz == mx)br += 1;
if(duz > mx){
mx = duz;
br = 1;
}
was[v] = 1;
int best = duz;
for(auto u : g[v]){
if(!was[u]){
int dist = dfs2(u, duz + 1);
// dia = max(dia, best + dist - 2 * duz);
if(best + dist - 2 * duz == dia)brdia += 1;
if(best + dist - 2 * duz > dia){
dia = best + dist - 2 * duz;
brdia = 1;
}
best = max(best, dist);
}
}
return best;
}
multiset<int> ms1;
void ins1(pii x){
int a = x.fi;
int b = x.se;
while(b--)ms1.insert(a);
}
void del1(pii x){
int a = x.fi;
int b = x.se;
while(b--)ms1.erase(ms1.find(a));
}
multiset<int> ms2;
void ins2(pii x){
int a = x.fi;
int b = x.se;
while(b--)ms2.insert(a);
}
void del2(pii x){
int a = x.fi;
int b = x.se;
while(b--)ms2.erase(ms2.find(a));
}
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[i] = {mx, br};
}
int len = sz(krug);
// max najmanju dist izmedju dva cvora
int dist = len / 2;
ins1(kol[0]);
int ans = 0;
int ima = 0;
// i - j <= len / 2
ff(i,1,dist - 1){
int a = kol[i].fi + i + *ms1.rbegin();
if(a == ans)ima += kol[i].se * ms1.count(*ms1.rbegin());
if(a > ans){
ans = a;
ima = kol[i].se * ms1.count(*ms1.rbegin());
}
// ms1.insert(kol[i].fi - i);
ins1({kol[i].fi - i, kol[i].se});
}
ff(i,dist,len - 1){
// ans = max(ans, kol[i].fi + i + *ms1.rbegin());
// cout << "i: " << i << endl;
int a = kol[i].fi + i + *ms1.rbegin();
// cout << "a: " << a << endl;
int x = *ms1.rbegin();
if(a == ans){
if(len % 2 == 0 && x == kol[i - dist].fi - (i - dist))ima += 2 * kol[i].se * ms1.count(x);
else ima += kol[i].se * ms1.count(x);
}
if(a > ans){
ans = a;
if(len % 2 == 0 && x == kol[i - dist].fi - (i - dist))ima = 2 * kol[i].se * ms1.count(x);
else ima = kol[i].se * ms1.count(x);
}
if(!ms2.empty()){
// ans = max(ans, kol[i].fi - i + *ms2.rbegin() + len);
int b = kol[i].fi - i + *ms2.rbegin() + len;
// cout << "b: " << b << endl;
if(b == ans)ima += kol[i].se * ms2.count(*ms2.rbegin());
if(b > ans){
ans = b;
ima = kol[i].se * ms2.count(*ms2.rbegin());
}
}
// cout << "------------------------" << endl;
// cout << endl;
// ms1.erase(ms1.find(kol[i - dist].fi - (i - dist)));
del1({kol[i - dist].fi - (i - dist), kol[i - dist].se});
// ms1.insert(kol[i].fi - i);
// ms2.insert(kol[i - dist].fi + (i - dist));
ins1({kol[i].fi - i, kol[i].se});
ins2({kol[i - dist].fi + (i - dist), kol[i - dist].se});
}
// i - j > len / 2
if(dia == ans)ima += brdia;
if(dia > ans)ima = brdia;
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 |
3 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 |
4 ms |
5100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
11372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
