#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
const int maxN = 1e6 + 10;
pii d[maxN];
long long ans;
long long ways = 1;
int n;
vector<int> v[maxN];
void dfs1(int x, int pred) {
d[x] = {0, 1};
for (int i: v[x]) {
if (i != pred) {
dfs1(i, x);
if (d[i].first + 1 > d[x].first) {
d[x] = {d[i].first + 1, d[i].second};
} else {
if (d[i].first + 1 == d[x].first) {
d[x].second+=d[i].second;
}
}
}
}
}
void dfs2(int x, int pred, pii bestUp) {
vector<pii> choices;
choices.pb(bestUp);
for (int i: v[x]) {
if (i != pred) {
choices.pb(d[i]);
}
}
sort(choices.begin(), choices.end());
reverse(choices.begin(), choices.end());
if (choices.size() > 2) {
long long maxProduct = 1ll * (choices[0].first + 1) * (choices[1].first + choices[2].first + 2);
if (maxProduct >= ans) {
long long pathCount = 0;
if (choices[1].first == choices[2].first) {
long long total = 0;
long long removeSum = 0;
for (auto i: choices) {
if (choices[1].first == i.first) {
total+=i.second;
removeSum+= 1ll * i.second * i.second;
}
}
pathCount = total * total - removeSum;
pathCount/=2;
} else {
if (choices[0].first == choices[1].first) {
long long total = 0;
for (auto i: choices) {
if (choices[2].first == i.first) {
total+=i.second;
}
}
pathCount = total * (choices[0].second + choices[1].second);
} else {
long long total = 0;
for (auto i: choices) {
if (choices[2].first == i.first) {
total+=i.second;
}
}
pathCount = total * choices[1].second;
}
}
if (maxProduct == ans) ways+=pathCount; else {
ans = maxProduct;
ways = pathCount;
}
}
}
// leaf
if (v[x].size() == 1 && pred) {
return;
}
int len = choices[0].first;
int nacini = 0;
int drugiNacini = 0;
for (auto i: choices) {
if (i.first == len) nacini+=i.second;
if (i.first == choices[1].first) drugiNacini+=i.second;
}
for (int i: v[x]) {
if (i != pred) {
if (d[i].first == len) {
if (nacini - d[i].second != 0) {
dfs2(i, x, {len + 1, nacini - d[i].second});
} else {
dfs2(i, x, {choices[1].first + 1, drugiNacini});
}
} else {
dfs2(i, x, {len + 1, nacini});
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i<n; i++) {
int x, y;
scanf("%d%d", &x, &y);
v[x].pb(y);
v[y].pb(x);
}
dfs1(1, 0);
dfs2(1, 0, {-1, 1});
cout << ans << " " << ways << endl;
return 0;
}
Compilation message
road.cpp: In function 'int main()':
road.cpp:138:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23744 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
23724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23744 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
23724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23744 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
23724 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
