// BEGIN BOILERPLATE CODE
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool kami_loc = true;
const long long kami_seed = 69420;
#else
const bool kami_loc = false;
const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif
const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);
long long rand_range(long long rmin, long long rmax) {
uniform_int_distribution<long long> rdist(rmin, rmax);
return rdist(kami_gen);
}
long double rand_real(long double rmin, long double rmax) {
uniform_real_distribution<long double> rdist(rmin, rmax);
return rdist(kami_gen);
}
void file_io(string fi, string fo) {
if (fi != "" && (!kami_loc || fi == kami_fi)) {
freopen(fi.c_str(), "r", stdin);
}
if (fo != "" && (!kami_loc || fo == kami_fo)) {
freopen(fo.c_str(), "w", stdout);
}
}
void set_up() {
if (kami_loc) {
file_io(kami_fi, kami_fo);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void just_do_it();
void just_exec_it() {
if (kami_loc) {
auto pstart = chrono::steady_clock::now();
just_do_it();
auto pend = chrono::steady_clock::now();
long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
string bar(50, '=');
cout << '\n' << bar << '\n';
cout << "Time: " << ptime << " ms" << '\n';
}
else {
just_do_it();
}
}
int main() {
set_up();
just_exec_it();
return 0;
}
// END BOILERPLATE CODE
// BEGIN MAIN CODE
const int ms = 5e5 + 20;
const int inf = 1e9 + 20;
vector<int> adj[ms];
pair<int, int> down[ms];
pair<int, int> up[ms];
pair<long long, long long> res;
struct group {
int sz = 0;
long long s1 = 0;
long long s2 = 0;
void add(int x) {
sz++;
s1 += x;
s2 += 1LL * x * x;
}
void rem(int x) {
sz--;
s1 -= x;
s2 -= 1LL * x * x;
}
};
struct merge_ {
map<int, group, greater<int>> f;
void add(pair<int, int> x) {
f[x.first].add(x.second);
}
void rem(pair<int, int> x) {
auto it = f.find(x.first);
it->second.rem(x.second);
if (it->second.sz == 0) {
f.erase(it);
}
}
pair<int, long long> best1() {
if (f.empty()) {
return {-inf, 0};
}
auto it = f.begin();
return {it->first, it->second.s1};
}
pair<int, long long> best2() {
if (f.empty()) {
return {-inf, 0};
}
auto it = f.begin();
int x = it->first;
long long s1 = it->second.s1;
long long s2 = it->second.s2;
if (it->second.sz > 1) {
return {x + x, (s1 * s1 - s2) / 2};
}
it++;
if (it == f.end()) {
return {-inf, 0};
}
int y = it->first;
s2 = it->second.s1;
return {x + y, s1 * s2};
}
};
merge_ g[ms];
pair<int, int> operator+(pair<int, int> x, int d) {
return {x.first + d, x.second};
}
pair<int, long long> operator+(pair<int, long long> x, pair<int, long long> y) {
if (x.first == -1 || y.first == 1) {
return {-1, 0};
}
return {x.first + y.first, x.second * y.second};
}
pair<long long, long long> operator*(pair<int, long long> x, int d) {
if (x.first == -1) {
return {-1, 0};
}
return {1LL * x.first * d, x.second};
}
pair<long long, long long> max(pair<long long, long long> x, pair<long long, long long> y) {
if (x.first > y.first) {
return x;
}
else if (x.first < y.first) {
return y;
}
else {
return {x.first, x.second + y.second};
}
}
pair<int, int> max(pair<int, int> x, pair<int, int> y) {
if (x.first > y.first) {
return x;
}
else if (x.first < y.first) {
return y;
}
else {
return {x.first, x.second + y.second};
}
}
void dfs1(int u, int pr) {
down[u] = {0, 1};
for (auto v: adj[u]) {
if (v != pr) {
dfs1(v, u);
down[u] = max(down[u], down[v] + 1);
}
}
}
void dfs2(int u, int pr) {
pair<int, int> mx;
for (auto v: adj[u]) {
if (v != pr) {
up[v] = max(up[u] + 1, mx + 2);
mx = max(mx, down[v]);
}
}
reverse(adj[u].begin(), adj[u].end());
mx = {0, 0};
for (auto v: adj[u]) {
if (v != pr) {
up[v] = max(up[v], mx + 2);
dfs2(v, u);
mx = max(mx, down[v]);
}
}
}
void dfs3(int u, int pr) {
for (auto v: adj[u]) {
if (v != pr) {
g[u].add(down[v] + 1);
}
}
if (pr != -1) {
res = max(res, g[u].best2() * up[u].first);
}
for (auto v: adj[u]) {
if (v != pr) {
g[u].rem(down[v] + 1);
res = max(res, g[u].best2() * (down[v].first + 1));
if (pr != -1) {
res = max(res, (g[u].best1() + up[u]) * (down[v].first + 1));
}
g[u].add(down[v] + 1);
}
}
for (auto v: adj[u]) {
if (v != pr) {
dfs3(v, u);
}
}
}
void just_do_it() {
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int root = -1;
bool pos = false;
for (int i = 1; i <= n; i++) {
int deg = adj[i].size();
if (deg >= 2) {
if (deg >= 3) {
pos = true;
}
}
else {
if (root == -1) {
root = i;
}
}
}
if (!pos) {
cout << "0 1";
return;
}
dfs1(root, -1);
up[root] = {0, 1};
dfs2(root, -1);
dfs3(root, -1);
cout << res.first << " " << res.second;
}
// END MAIN CODE
Compilation message
road.cpp: In function 'void file_io(std::string, std::string)':
road.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | freopen(fi.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen(fo.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
35492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
