This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(v) (int)(v).size()
#define pii pair<int, int>
using namespace std;
const int MXn = 500005;
void make_better(int &A, int &B, int x, int y) {
if (A < x) {
A = x;
B = y;
} else if (A == x) {
B += y;
}
}
pii get_better(int A, int B, int x, int y) {
if (A < x) {
A = x;
B = y;
} else if (A == x) {
B += y;
}
return {A, B};
}
int n;
vector<int> adj[MXn];
int mx[MXn], cnt[MXn];
void DFS1(int u, int par) {
mx[u] = 0, cnt[u] = 1;
for (int v: adj[u]) if (v != par) {
DFS1(v, u);
make_better(mx[u], cnt[u], mx[v] + 1, cnt[v]);
}
}
int H = 0, dem = 1;
void DFS2(int u, int par, int Mx, int Cnt) {
vector<tuple<int, int, int>> nah;
vector<pii> paths;
if (Mx) {
paths.emplace_back(Mx, Cnt);
}
for (int v: adj[u]) if (v != par) {
nah.emplace_back(v, mx[v] + 1, cnt[v]);
paths.emplace_back(mx[v] + 1, cnt[v]);
}
sort(begin(paths), end(paths), greater<pii>());
if (sz(paths) >= 3) {
int z = paths[0].fi, y = paths[1].fi, x = paths[2].fi;
int h = z * (x + y);
// cerr << u << ' ' << h;
if (H <= h) {
int Dz = paths[0].se, Dy = paths[1].se, Dx = paths[2].se;
// cerr << ' ' << Dx << ' ' << Dy << ' ' << Dz;
int Dem = 0;
if (x < y && y < z) {
for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) Dx += paths[i].se;
Dem = Dx * Dy;
} else if (x == y && y < z) {
// Dem = ((Dx + Dy) * (Dx + Dy - 1) / 2) - Dx * (Dx - 1) / 2 - Dy * (Dy - 1) / 2;
Dem = Dy * Dx;
int tmp = Dy + Dx;
for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) {
Dem += tmp * paths[i].se;
tmp += paths[i].se;
}
} else if (x < y && y == z) {
for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) Dx += paths[i].se;
Dem = Dx * (Dy + Dz);
} else if (x == y && y == z) {
Dem = Dz * Dy + (Dz + Dy) * Dx;
int tmp = Dx + Dy + Dz;
for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) {
Dem += tmp * paths[i].se;
tmp += paths[i].se;
}
}
make_better(H, dem, h, Dem);
}
// cerr << '\n';
}
vector<pii> s;
if (sz(nah)) {
s.resize(sz(nah));
s.back() = {(get<1>(nah.back())) + 1, get<2>(nah.back())};
for (int i = sz(nah) - 2; i >= 0; i--) {
s[i] = get_better(s[i + 1].fi, s[i + 1].se, (get<1>(nah[i])) + 1, get<2>(nah[i]));
}
}
pii p = {Mx + 1, Cnt};
for (int i = 0; i < sz(nah); i++) {
pii New = p;
if (i != sz(nah) - 1) New = get_better(New.fi, New.se, s[i + 1].fi, s[i + 1].se);
DFS2(get<0>(nah[i]), u, New.fi, New.se);
p = get_better(p.fi, p.se, (get<1>(nah[i])) + 1, get<2>(nah[i]));
}
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
DFS1(1, 0);
DFS2(1, 0, 0, 1);
cout << H << ' ' << dem;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |