This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())
const int maxn = 5e5 + 5;
const int inf = 1e9 + 7;
ll n, cnt[maxn];
pll dpu[maxn], dpd[maxn];
pll ans = mp(0, 1);
vector<int> adj[maxn];
void smaxp(pll &x, pll y, int v){
if(y.F + v > x.F) x = mp(y.F + v, y.S);
else if(y.F + v == x.F) x.S += y.S;
}
void dfsd(int v = 1, int p = 0){
dpd[v] = mp(0, 1);
for(auto u: adj[v]) if(u != p){
dfsd(u, v);
smaxp(dpd[v], dpd[u], 1);
}
}
void dfsu(int v = 1, int p = 0){
int mx1 = -1, mx2 = -1;
for(auto u: adj[v]) if(u != p){
if(mx1 == -1 || dpd[u].F >= dpd[mx1].F){
mx2 = mx1;
mx1 = u;
}
else if(mx2 == -1 || dpd[u].F > dpd[mx2].F) mx2 = u;
smaxp(dpu[u], dpu[v], 1);
}
for(auto u: adj[v]) if(u != p){
if(u == mx1){
if(mx2 != -1){
smaxp(dpu[u], dpd[mx2], 2);
}
}
else smaxp(dpu[u], dpd[mx1], 2);
dfsu(u, v);
}
}
void dfs(int v = 1, int p = 0){
vector<pll> vec;
for(auto u: adj[v]) if(u != p){
dfs(u, v);
vec.pb(mp(dpd[u].F + 1, dpd[u].S));
}
if(v > 1) vec.pb(dpu[v]);
if(vec.size() < 3) return;
sort(all(vec), greater<>());
ll val = vec[1].F + vec[2].F;
ll res = 0;
for(int i = 1; i < vec.size(); i++){
res += vec[i].S * cnt[val - vec[i].F];
cnt[vec[i].F] += vec[i].S;
}
if(vec[2].F == vec[0].F){
for(int i = 1; i < vec.size() && vec[i].F == vec[0].F; i++){
res += vec[i].S * vec[0].S;
}
}
else if(vec[1].F == vec[0].F){
res += (res / vec[1].S) * vec[0].S;
}
smaxp(ans, mp(vec[0].F * val, res), 0);
for(auto u: vec) cnt[u.F] = 0;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n - 1; i++){
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfsd();
for(int i = 1; i <= n; i++) dpu[i] = mp(0, 1);
dfsu();
// for(int i = 1; i <= n; i++){
// cout << i << ' ' << dpd[i].F << ' ' << dpd[i].S << ' ' << dpu[i].F << ' ' << dpu[i].S << '\n';
// }
dfs();
cout << ans.F << ' ' << ans.S << '\n';
return 0;
}
Compilation message (stderr)
road.cpp: In function 'void dfs(int, int)':
road.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 1; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
road.cpp:82:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i = 1; i < vec.size() && vec[i].F == vec[0].F; i++){
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |