#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
vector<vector<int>> g;
vector<vector<pi>> v;
vector<pi> tot;
pi dfs(int i, int p) {
if (g[i].size() == 1) v[i].emplace_back(0, 1);
for (int j : g[i]) if (j != p) {
pi tmp = dfs(j, i);
++tmp.first;
v[i].push_back(tmp);
if (tmp.first > tot[i].first) tot[i] = tmp;
else if (tmp.first == tot[i].first) tot[i].second += tmp.second;
}
return tot[i];
}
pair<ll, ll> ans;
void upd(int i) {
sort(all(v[i]), [](pi i, pi j){return i.first > j.first;});
if (v[i].size() < 3) return;
ll tmp = v[i][0].first * ll(v[i][1].first + v[i][2].first);
if (tmp < ans.first) return;
if (tmp > ans.first) ans = make_pair(tmp, 0);
ll dp[3]{};
for (int j = 0; j < v[i].size() && v[i][j].first >= v[i][2].first; ++j) {
if (v[i][j].first == v[i][2].first)
dp[2] += dp[1] * v[i][j].second;
if (v[i][j].first == v[i][1].first)
dp[1] += dp[0] * v[i][j].second;
if (v[i][j].first == v[i][0].first)
dp[0] += v[i][j].second;
}
if (v[i][2].first == v[i][0].first) ans.second += dp[1];
else if (v[i][1].first == v[i][0].first) ans.second += 2 * dp[2];
else ans.second += dp[2];
}
void dfs2(int i, int p) {
if (~p) {
pi tmp = tot[p];
if (tmp.first == tot[i].first + 1) tmp.second -= tot[i].second;
if (tmp.second == 0) {
if (v[p].size() == 1) goto f1;
tmp = v[p][1];
for (int j = 2; j < v[p].size() && v[p][j].first == tmp.first; ++j)
tmp.second += v[p][j].second;
}
++tmp.first;
v[i].push_back(tmp);
if (tmp.first > tot[i].first) tot[i] = tmp;
else if (tmp.first == tot[i].first) tot[i].second += tmp.second;
}
f1:
upd(i);
for (int j : g[i]) if (j != p) dfs2(j, i);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
g.resize(n), v.resize(n), tot.assign(n, pi(0, 1));
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y), g[y].push_back(x);
}
dfs(0, -1);
dfs2(0, -1);
if (ans.first) cout << ans;
else cout << "0 1";
}
Compilation message
road.cpp: In function 'void upd(int)':
road.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int j = 0; j < v[i].size() && v[i][j].first >= v[i][2].first; ++j) {
| ~~^~~~~~~~~~~~~
road.cpp: In function 'void dfs2(int, int)':
road.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int j = 2; j < v[p].size() && v[p][j].first == tmp.first; ++j)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
