#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
int N;
pair<ll, ll> ans;
vector<vector<int>> adj_list;
// Inside variables
int leafs = 0;
vector<pi> total_best;
vector<pi> first_inside;
vector<int> topkid;
vector<pi> second_inside;
vector<pi> third_inside;
// Outside variables
vector<pi> path_outside;
pi operator + (pi a, pi b)
{
if (a.f > b.f)
return a;
if (b.f > a.f)
return b;
return mp(a.f, b.s + a.s);
}
pair<ll, ll> operator + (pair<ll, ll> a, pair<ll, ll> b)
{
if (b.s <= 0)
return a;
if (a.s <= 0)
return b;
if (a.f > b.f)
return a;
if (b.f > a.f)
return b;
return mp(a.f, b.s + a.s);
}
void calculate_inside(int node, int par)
{
pi p1 = mp(0, 0), p2 = mp(0, 0), p3 = mp(0, 0);
if (adj_list[node].size() == 1) {
p1.s = 1;
leafs++;
}
total_best[node].s = 1;
for (auto neigh : adj_list[node]) {
if (neigh == par)
continue;
calculate_inside(neigh, node);
if (p1.f == total_best[neigh].f + 1) {
total_best[node].s++;
}
if (p1.f < total_best[neigh].f + 1) {
topkid[node] = neigh;
total_best[node].s = 1;
p3 = p2;
p2 = p1;
p1 = mp(total_best[neigh].f + 1, total_best[neigh].s);
}
else if (p2.f < total_best[neigh].f + 1) {
p3 = p2;
p2 = mp(total_best[neigh].f + 1, total_best[neigh].s);
}
else if (p3.f < total_best[neigh].f + 1) {
p3 = mp(total_best[neigh].f + 1, total_best[neigh].s);
}
}
total_best[node].f = p1.f;
first_inside[node] = p1;
second_inside[node] = p2;
third_inside[node] = p3;
}
void try_triplet(pi a, pi b, pi c)
{
int p1, p2, p3;
int c1, c2, c3;
tie(p1, c1) = a;
tie(p2, c2) = b;
tie(p3, c3) = c;
ll chances = (ll)c1 * c2 * c3;
ans = ans + mp((ll)p1 * (p2 + p3), (ll)c2 * c3);
ans = ans + mp((ll)p2 * (p1 + p3), (ll)c1 * c3);
ans = ans + mp((ll)p3 * (p2 + p1), (ll)c2 * c1);
}
void calculate_outside(int node, int par)
{
if (par != -1) {
path_outside[node] = path_outside[par];
if (topkid[par] != node) {
path_outside[node] = path_outside[node] + first_inside[par];
}
else {
path_outside[node] = path_outside[node] + second_inside[par];
}
path_outside[node].f++;
}
// Assume the current node is the one that contains the hardness value
try_triplet(first_inside[node], second_inside[node], third_inside[node]);
try_triplet(first_inside[node], second_inside[node], path_outside[node]);
try_triplet(first_inside[node], third_inside[node], path_outside[node]);
try_triplet(second_inside[node], third_inside[node], path_outside[node]);
for (auto neigh : adj_list[node])
if (neigh != par)
calculate_outside(neigh, node);
}
int main(void)
{
scanf("%d", &N);
adj_list.resize(N);
first_inside.resize(N);
second_inside.resize(N);
third_inside.resize(N);
path_outside.resize(N);
total_best.resize(N);
topkid.assign(N, -1);
for (int i = 0; i < N - 1; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
adj_list[a].pb(b);
adj_list[b].pb(a);
}
calculate_inside(0, -1);
calculate_outside(0, -1);
if (ans.f == 0)
ans.s = (ll)leafs * (leafs - 1) / 2;
printf("%lld %lld\n", ans.f, ans.s);
return 0;
}
Compilation message
road.cpp: In function 'void try_triplet(pi, pi, pi)':
road.cpp:103:8: warning: unused variable 'chances' [-Wunused-variable]
103 | ll chances = (ll)c1 * c2 * c3;
| ^~~~~~~
road.cpp: In function 'int main()':
road.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
road.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
300 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
300 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
300 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
300 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
300 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
300 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
