Submission #93298

#TimeUsernameProblemLanguageResultExecution timeMemory
93298toloraiaHard route (IZhO17_road)C++14
52 / 100
2056 ms58516 KiB
#include <bits/stdc++.h> #define ll long long #define F first #define S second using namespace std; const int N = 5e5 + 5; int n; vector < int > g[N]; ll ans = -1, num; ll D[N]; void dfs (int k, int p){ D[k] = 0; for (int u: g[k]){ if (u == p) continue; dfs (u, k); D[k] = max (D[k], D[u]); } D[k]++; } void go (int k, int p, ll d, ll dd){ if ((int)g[k].size() == 1 && p != 0){ if (ans == d * dd) num++; if (ans < d * dd){ ans = d * dd; num = 1; } } ll x = 0, y = 0; for (int u: g[k]){ if (u == p) continue; y = max (y, D[u]); if (x < y) swap (x, y); } for (int u: g[k]){ if (u == p) continue; ll t = x; if (t == D[u]) t = y; go (u, k, d + 1, max (dd, t)); } } int main() { ios::sync_with_stdio(false); cin>>n; for (int i = 1; i < n; i++){ int u, v; cin>>u>>v; g[u].push_back (v); g[v].push_back (u); } for (int S = 1; S <= n; S++){ if ((int)g[S].size() > 1) continue; dfs (S, 0); go (S, 0, 0, 0); } cout<<ans<<" "<<num / 2<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...