#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<vector<int>> adj(N);
for (int i = 1; i < N; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
// Let's fix a node u, and consider the 3 maximum distances
// from u (where each is from different children). WLOG,
// a <= b <= c. Then, the optimal hardness is c * (a + b).
//
// For (a, b, c) and node u, note that we can canonize the
// route (a, b). For a fixed route (a, b), there might be
// a lot of count(max(c)). However, if there is more than
// 1 occurrence of length at least c, then at node u it
// wouldn't be (a, b, c); instead it would be (a, c + x, c),
// (we extend b to instead use the c-route since it's longer),
// so it would be a different route. This way, c is unique
// for a route (a, b) and only counted once.
//
// Now, we can use dynamic programming to count (a, b, c) in O(N).
using lint = long long;
array<lint, 2> ans = {0, 0};
vector<array<lint, 2>> dn(N);
vector<array<lint, 2>> up(N);
const auto Add = [&](array<lint, 2> p, array<lint, 2> q) -> array<lint, 2> {
if (p[0] != q[0]) return max(p, q);
return {p[0], p[1] + q[1]};
};
const auto DfsDn = [&](const auto &self, int u, int p) -> void {
dn[u] = {0, 1};
for (auto v : adj[u]) if (v != p) {
self(self, v, u);
dn[u] = Add(dn[u], {dn[v][0] + 1, dn[v][1]});
}
};
const auto DfsUp = [&](const auto &self, int u, int p) -> void {
array<lint, 2> cur[2];
cur[0] = up[u];
cur[1] = {0, 0};
for (auto v : adj[u]) if (v != p) {
bool added = false;
for (int i = 0; i < 2; i++) {
if (cur[i][0] == dn[v][0] + 1) {
cur[i][1] += dn[v][1];
added = true;
break;
}
}
if (!added && dn[v][0] + 1 > cur[1][0]) {
cur[1] = {dn[v][0] + 1, dn[v][1]};
if (cur[1] > cur[0]) swap(cur[0], cur[1]);
}
}
for (auto v : adj[u]) if (v != p) {
if (dn[v][0] + 1 == cur[0][0] && dn[v][1] == cur[0][1]) {
up[v][0] = cur[1][0] + 1;
up[v][1] = cur[1][1];
} else if (dn[v][0] + 1 == cur[0][0]) {
up[v][0] = cur[0][0] + 1;
up[v][1] = cur[0][1] - dn[v][1];
} else {
up[v][0] = cur[0][0] + 1;
up[v][1] = cur[0][1];
}
self(self, v, u);
}
};
const auto DfsSolve = [&](const auto &self, int u, int p) -> void {
array<lint, 4> cur[3];
// (length, cnt, cnt if pick 2 different child, cnt if pick 3 different child)
cur[0] = {up[u][0], up[u][1], 0, 0};
cur[1] = {0, 0, 0, 0};
cur[2] = {0, 0, 0, 0};
for (auto v : adj[u]) if (v != p) {
self(self, v, u);
bool added = false;
for (int i = 0; i < 3; i++) {
if (cur[i][0] == dn[v][0] + 1) {
cur[i][3] += dn[v][1] * cur[i][2];
cur[i][2] += dn[v][1] * cur[i][1];
cur[i][1] += dn[v][1];
added = true;
break;
}
}
if (!added && dn[v][0] + 1 > cur[2][0]) {
cur[2] = {dn[v][0] + 1, dn[v][1], 0, 0};
if (cur[2] > cur[1]) swap(cur[1], cur[2]);
if (cur[1] > cur[0]) swap(cur[0], cur[1]);
}
}
if (cur[0][3] != 0) { // Case a = b = c
ans = Add(ans, {cur[0][0] * (cur[0][0] + cur[0][0]), cur[0][2]});
} else if (cur[0][2] != 0) { // Case a < b = c
ans = Add(ans, {cur[0][0] * (cur[0][0] + cur[1][0]), cur[0][1] * cur[1][1]});
} else if (cur[1][2] != 0) { // Case a = b < c
ans = Add(ans, {cur[0][0] * (cur[1][0] + cur[1][0]), cur[1][2]});
} else { // Case a < b < c
ans = Add(ans, {cur[0][0] * (cur[1][0] + cur[2][0]), cur[1][1] * cur[2][1]});
}
};
int root = -1;
for (int i = 0; i < N; i++) {
if (adj[i].size() > 2) {
root = i;
break;
}
}
if (root == -1) { // tree is line graph
cout << 0 << ' ' << 1 << '\n';
return 0;
}
DfsDn(DfsDn, root, -1);
DfsUp(DfsUp, root, -1);
DfsSolve(DfsSolve, root, -1);
assert(ans[0] != 0);
cout << ans[0] << ' ' << ans[1] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
