제출 #759826

#제출 시각아이디문제언어결과실행 시간메모리
759826NK_Hard route (IZhO17_road)C++17
0 / 100
1 ms340 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define f first #define s second #define mp make_pair #define nl '\n' #define pb push_back #define sz(x) int(x.size()) using pi = pair<int, int>; using ll = long long; template<class T> using V = vector<T>; template<class T> using mset = multiset<T>; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; V<V<int>> adj(N); V<int> deg(N); int T = 0; for(int i = 0; i < N-1; i++) { int u, v; cin >> u >> v; --u, --v; adj[u].pb(v); adj[v].pb(u); deg[u]++, deg[v]++; } int R = -1; for(int i = N-1; i >= 0; i--) { if (deg[i] > 1) R = i; else T++; } if (R == -1) { cout << 0 << " " << 1 << nl; return 0; } ll ans = 0, ways = T * (T - 1) / 2; V<pi> dp(N); V<map<int, int>> chd(N); function<void(int, int)> gen = [&](int u, int p) { for(auto v : adj[u]) if (v != p) { gen(v, u); chd[u][dp[v].f] += dp[v].s; }; if (sz(chd[u])) { dp[u] = *rbegin(chd[u]); dp[u].f++; } else dp[u] = mp(0, 1); }; gen(R, -1); auto upd = [&](int u, int k, int v) { chd[u][k] += v; if (chd[u][k] == 0) chd[u].erase(k); if (sz(chd[u])) { dp[u] = *rbegin(chd[u]); dp[u].f++; } else dp[u] = mp(0, 1); }; function<void(int, int)> dfs = [&](int u, int p) { // cout << "NODE: " << u << " " << p << endl; V<pi> chd = {}; for(auto v : adj[u]) chd.pb(dp[v]); sort(rbegin(chd), rend(chd)); // if (p != -1 && size(chd) >= 2) { // // C is from above // int a = chd[0].f, b = chd[1].f; // ll R = 0; // if (a == b) { // ll sum = 0; for(auto x : chd) if (x.f == a) sum += x.s; // for(auto x : chd) R += (sum -= x.s) * x.s; // } else { // ll sum = 0; for(auto x : chd) if (x.f == b) sum += x.s; // R += sum * 1LL * chd[0].s; // } // int c = dp[p].f; // ll H = c * (a + b); // } // // All 3 are children // if (size(chd) >= 3) { // int a = chd[0].f, b = chd[1].f, c = chd[2].f; // if (a == b && b == c) { // ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == a) sum += x.s, cnt++; // for(auto x : chd) R += (sum -= x.s) * x.s * (cnt - 2); // } // } if (size(chd) >= 3) { int a, at; tie(a, at) = chd[0]; int b, bt; tie(b, bt) = chd[1]; int c, ct; tie(c, ct) = chd[2]; ll R = 0; if (a == b && b == c) { ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == a) sum += x.s, cnt++; for(auto x : chd) if (x.f == a) R += (sum -= x.s) * 1LL * x.s * 1LL * (cnt - 2); } if (a != b && b == c) { ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == b) sum += x.s, cnt++; // cout << sum << " - " << cnt << nl; for(auto x : chd) if (x.f == b) R += (sum -= x.s) * 1LL * x.s; } if (a == b && b != c) { ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == c) sum += x.s, cnt++; R += sum * 1LL * (at + bt); } if (a != b && b != c) { R += bt * 1LL * ct; } ++a, ++b, ++c; // cout << a << " - " << b << " - " << c << endl; // cout << at << " - " << bt << " - " << ct << endl; ll H = (c + b) * 1LL * a; // cout << "(H, R) -> (" << H << ", " << R << ") " << endl; if (ans < H) ans = H, ways = 0; if (ans == H) ways += R; } for(auto v : adj[u]) if (v != p) { upd(u, dp[v].f, -dp[v].s); upd(v, dp[u].f, dp[u].s); dfs(v, u); upd(v, dp[u].f, -dp[u].s); upd(u, dp[v].f, dp[v].s); } }; dfs(R, -1); cout << ans << " " << ways << nl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...