#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 Item = pair<long long, long long>;
Item ans = {0, 1};
vector<Item> dn(N);
vector<Item> up(N);
const auto Add = [&](Item p, Item q) {
if (p.first != q.first) return max(p, q);
return Item(p.first, p.second + q.second);
};
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].first + 1, dn[v].second});
}
};
const auto DfsUp = [&](const auto &self, int u, int p) -> void {
Item cur[2];
cur[0] = up[u];
cur[1] = {0, 0};
for (auto v : adj[u]) if (v != p) {
Item tmp = Item(dn[v].first + 1, dn[v].second);
if (tmp.first > cur[0].first) {
cur[1] = cur[0];
cur[0] = tmp;
} else if (tmp.first == cur[0].first) {
cur[0] = Add(cur[0], tmp);
} else {
cur[1] = Add(cur[1], tmp);
}
}
for (auto v : adj[u]) if (v != p) {
if (dn[v].first + 1 == cur[0].first && dn[v].second == cur[0].second) {
up[v].first = cur[1].first + 1;
up[v].second = cur[1].second;
} else if (dn[v].first + 1 == cur[0].first) {
up[v].first = cur[0].first + 1;
up[v].second = cur[0].second - dn[v].second;
} else {
up[v].first = cur[0].first + 1;
up[v].second = cur[0].second;
}
self(self, v, u);
}
};
const auto DfsSolve = [&](const auto &self, int u, int p) -> void {
array<long long, 4> cur[3];
// (length, cnt, cnt if pick 2 different child, cnt if pick 3 different child)
cur[0] = {up[u].first, up[u].second, 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].first + 1) {
cur[i][3] += dn[v].second * cur[i][2];
cur[i][2] += dn[v].second * cur[i][1];
cur[i][1] += dn[v].second;
added = true;
break;
}
}
if (!added && dn[v].first + 1 > cur[2][0]) {
cur[2] = {dn[v].first + 1, dn[v].second, 0, 0};
if (cur[2][0] > cur[1][0]) swap(cur[1], cur[2]);
if (cur[1][0] > cur[0][0]) swap(cur[0], cur[1]);
}
}
if (cur[0][3] != 0) { // Case a = b = c
ans = Add(ans, Item(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, Item(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, Item(cur[0][0] * (cur[1][0] + cur[1][0]), cur[1][2]));
} else { // Case a < b < c
ans = Add(ans, Item(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;
}
}
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);
cout << ans.first << ' ' << ans.second << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
312 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 |
316 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
312 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 |
316 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
312 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 |
316 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
