| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 763989 | nonono | Hard route (IZhO17_road) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#define int long long
using namespace std;
void file(string name = ""){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(name != ""){
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
void _max(pair<int, int> &a, pair<int, int> b){
if(a.first < b.first){
a = b;
} else
if(a.first == b.first){
a.second += b.second;
}
}
const int mxN = 5e5 + 10;
int n;
vector<vector<int>> adj(mxN);
pair<int, int> d[mxN], f[mxN], pref[mxN], suff[mxN];
int max_hardness = 0, count_path = 1;
void dfs(int u, int p){
d[u] = {0, 1};
for(int v : adj[u]){
if(v == p) continue ;
dfs(v, u);
_max(d[u], make_pair(d[v].first + 1, d[v].second));
}
}
void _dfs(int u, int p){
vector<int> b;
vector<pair<int, int>> a;
if(adj[u].size() == 1 || u > 1){
a.push_back({f[u].first + 1, f[u].second});
}
for(int v : adj[u]){
if(v == p) continue ;
a.push_back({d[v].first + 1, d[v].second});
}
sort(a.begin(), a.end(), greater<pair<int, int>> ());
if(a.size() >= 3 && a[0].first * (a[1].first + a[2].first) >= max_hardness){
int curr_hardness = a[0].first * (a[1].first + a[2].first);
int curr_path = 0;
int cnt = 0;
for(auto [x, y] : a){
if(x == a[2].first){
cnt += y;
}
}
if(a[1].first == a[2].first){
curr_path = cnt * cnt;
for(auto [x, y] : a){
if(x == a[2].first){
curr_path -= y * y;
}
}
curr_path /= 2;
} else
if(a[0].first == a[1].first){
curr_path = (a[0].second + a[1].second) * cnt;
} else {
curr_path = a[1].second * cnt;
}
if(curr_hardness > max_hardness){
max_hardness = curr_hardness;
count_path = curr_path;
} else {
count_path += curr_path;
}
}
a.clear();
for(int v : adj[u]){
if(v == p) continue ;
a.push_back({d[v].first + 1, d[v].second});
b.push_back(v);
}
pref[0] = {0, 0};
for(int i = 1; i <= a.size(); i ++){
pref[i] = pref[i - 1];
_max(pref[i], a[i - 1]);
}
suff[a.size() + 1] = {0, 0};
for(int i = a.size(); i >= 1; i --){
suff[i] = suff[i + 1];
_max(suff[i], a[i - 1]);
}
for(int i = 1; i <= a.size(); i ++){
int v = b[i - 1];
_max(f[v], pref[i - 1]);
_max(f[v], suff[i + 1]);
if(adj[u].size() == 1 || u > 1) _max(f[v], f[u]);
}
for(int i = 1; i <= a.size(); i ++){
int v = b[i - 1];
_dfs(v, u);
}
}
int main(){
file("");
cin >> n;
for(int i = 1; i <= n - 1; i ++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
f[1] = {0, 1};
_dfs(1, 1);
cout << max_hardness << " " << count_path << "\n";
return 0;
}