#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
const int MAXN = 5e5 + 25;
vector <int> adj[MAXN];
vector <int> dp[MAXN];
int n;
int mx = 0, cnt = 0;
int mx2 = 0, cnt2 = 0;
void upd (int x) {
if (x > mx) {
mx = x; cnt = 1;
} else if (x == mx) cnt++;
}
void upd2 (int x) {
if (x > mx2) {
mx2 = x; cnt2 = 1;
} else if (x == mx2) {
cnt2++;
}
}
void dfs (int pos, int par, int dep = 0) {
dp[pos].clear();
if (adj[pos].size() == 1 && par != -1) {
dp[pos].push_back(0);
upd(0);
return;
}
for (auto j : adj[pos]) {
if (j == par) continue;
dfs(j, pos, dep + 1);
for (auto i : dp[j]) {
dp[pos].push_back(i + 1);
}
}
sort(dp[pos].begin(), dp[pos].end());
reverse(dp[pos].begin(), dp[pos].end());
if (dp[pos].size() > 1) {
upd((dep + dp[pos][0]) * dp[pos][1]);
upd((dep + dp[pos][1]) * dp[pos][0]);
}
if (par == -1) {
upd2(dp[pos][0]);
}
//cout << pos << " " << par << " " << dep << ": "; for (auto j : dp[pos]) cout << j << " ";
//cout << '\n';
dp[pos].resize(1);
}
int main () {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (adj[i].size() == 1) {
//cout << " " << i << ": \n";
dfs(i, -1);
}
}
if (mx > mx2) {
cout << mx << " " << cnt / 2 << '\n';
} else if (mx2 > mx) {
cout << mx2 << " " << cnt2 << '\n';
} else {
cout << mx << " " << cnt2 + cnt / 2 << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
23900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
23900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
23900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
