제출 #941424

#제출 시각아이디문제언어결과실행 시간메모리
941424TAhmed33Hard route (IZhO17_road)C++98
52 / 100
100 ms1136 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf = -1e9; const int MAXN = 5e3 + 25; vector <int> adj[MAXN]; int n; ll mx = 0, cnt = 1; pair <ll, ll> dfs (int pos, int par, int dep) { if (par != -1 && adj[pos].size() == 1) { return {0, 1}; } pair <ll, ll> d1 = {inf, 0}, d2 = {inf, 0}; pair <ll, ll> ret = {inf, 0}; bool flag = 0; for (auto j : adj[pos]) { if (j == par) continue; auto h = dfs(j, pos, dep + 1); h.first += 1; if (h.first > d1.first) { d2 = d1; d1 = h; } else if (h.first == d1.first) { d1.second += h.second; } else if (h.first > d2.first) { d2 = h; } else if (h.first == d2.first) { d2.second += h.second; } if (h.first > ret.first) { ret = h; flag = 0; } else if (h.first == ret.first) { ret.second += h.second; flag = 1; } } if (flag) { ll t = (dep + d1.first) * d1.first, s = ret.second; if (t > mx) { mx = t; cnt = s; } else if (t == mx) { cnt += s; } return ret; } ll t = (dep + d2.first) * d1.first, s = d2.second; if (t > mx) { mx = t; cnt = s; } else if (t == mx) { cnt += s; } return ret; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } for (int i = 1; i <= n; i++) { if ((int)adj[i].size() == 1) { dfs(i, -1, 0); } } if (mx == 0) { cout << "0 1\n"; return 0; } cout << mx << " " << cnt / 2 << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...