#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
const int N = 5e5;
struct Best {
ll mx;
ll freq;
};
vector <int> gr[1 + N];
int n;
Best dpDown[1 + N], dpUp[1 + N];
void updateBest (Best &ans, Best cur) {
if (cur.freq == 0) return;
if (ans.mx < cur.mx) {
ans = cur;
}
else if (ans.mx == cur.mx)
ans.freq += cur.freq;
}
void dfsDown (int node, int par) {
dpDown[node] = {0, 1};
for (int son : gr[node])
if (son != par) {
dfsDown (son, node);
updateBest (dpDown[node], {dpDown[son].mx + 1, dpDown[son].freq});
}
}
Best pref[1 + N], suff[1 + N];
void dfsUp (int node, int par) {
int sz = gr[node].size ();
for (int i = 0; i < sz; i++) {
int son = gr[node][i];
pref[i] = {0, 0};
if (i > 0)
pref[i] = pref[i - 1];
if (son != par)
updateBest (pref[i], {dpDown[son].mx + 2, dpDown[son].freq});
}
for (int i = sz - 1; i >= 0; i--) {
int son = gr[node][i];
suff[i] = {0, 0};
if (i < sz - 1)
suff[i] = suff[i + 1];
if (son != par)
updateBest (suff[i], {dpDown[son].mx + 2, dpDown[son].freq});
}
for (int i = 0; i < sz; i++) {
int son = gr[node][i];
if (son != par) {
updateBest (dpUp[son], {dpUp[node].mx + 1, dpUp[node].freq});
if (i > 0)
updateBest (dpUp[son], pref[i - 1]);
if (i < sz - 1)
updateBest (dpUp[son], suff[i + 1]);
dfsUp (son, node);
}
}
}
bool cmp (Best a, Best b) {
return a.mx > b.mx;
}
struct Help {
ll mx;
ll freq;
ll cnt;
};
ll dp[3];
Best ans;
void solve (int node, int par) {
vector <Best> edges;
for (int son : gr[node])
if (son != par)
edges.pb ({dpDown[son].mx + 1, dpDown[son].freq});
if (dpUp[node].mx > 0)
edges.pb (dpUp[node]);
sort (edges.begin (), edges.end (), cmp);
while (edges.size () >= 3 && edges.back ().mx < edges[2].mx)
edges.pop_back ();
if (edges.size () >= 3) {
vector <Help> good;
for (int i = 0; i < edges.size (); i++) {
int j = i;
ll freq = 0;
while (j < edges.size () && edges[i].mx == edges[j].mx) {
freq += edges[j].freq;
j++;
}
good.pb ({edges[i].mx, freq, j - i});
i = j;
}
if (good.size () == 1) {
dp[1] = dp[2] = 0;
for (Best edge : edges) {
ll dp1 = dp[1] + edge.freq;
ll dp2 = dp[2] + dp[1] * edge.freq;
dp[1] = dp1; dp[2] = dp2;
}
updateBest (ans, {2 * good[0].mx * good[0].mx, dp[2]});
}
else if (good.size () == 2) {
if (good[0].cnt > 1)
updateBest (ans, {good[0].mx * (good[0].mx + good[1].mx), good[0].freq * good[1].freq});
else {
dp[1] = dp[2] = 0;
for (Best edge : edges) {
if (edge.mx == good[1].mx) {
ll dp1 = dp[1] + edge.freq;
ll dp2 = dp[2] + dp[1] * edge.freq;
dp[1] = dp1; dp[2] = dp2;
}
}
updateBest (ans, {2 * good[0].mx * good[1].mx, dp[2]});
}
}
else {
updateBest (ans, {good[0].mx * (good[1].mx + good[2].mx), good[1].freq * good[2].freq});
}
}
for (int son : gr[node])
if (son != par)
solve (son, node);
}
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
gr[x].pb (y);
gr[y].pb (x);
}
int root = 0;
for (int i = 1; i <= n; i++)
if (gr[i].size () > 1)
root = i;
ans = {0, 1};
if (root) {
dfsDown (root, 0);
dpUp[root] = {-n, 0};
dfsUp (root, 0);
solve (root, 0);
}
cout << ans.mx << " " << ans.freq;
return 0;
}
Compilation message
road.cpp: In function 'void solve(int, int)':
road.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Best>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < edges.size (); i++) {
| ~~^~~~~~~~~~~~~~~
road.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Best>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | while (j < edges.size () && edges[i].mx == edges[j].mx) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12160 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12032 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12192 KB |
Output is correct |
| 6 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 7 |
Incorrect |
8 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12160 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12032 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12192 KB |
Output is correct |
| 6 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 7 |
Incorrect |
8 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12160 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12032 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12192 KB |
Output is correct |
| 6 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 7 |
Incorrect |
8 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
