#include <bits/stdc++.h>
//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
using namespace std;
//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 gen(time(0));
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long
const int N = 1e6 + 100;
const int M = 31;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
vector < int > g[N];
int leaf[N], ra[N], h[N], up[N], pred[N];
void DFS(int v, int pr)
{
pred[v] = pr;
h[v] = 0;
for(auto to: g[v])
{
if (to == pr) continue;
DFS(to, v);
h[v] = max(h[v], h[to] + 1);
}
}
void dfs(int v, int pr, int c)
{
int mx = -2, sr = -2;
for(auto to: g[v])
{
if (to == pr) continue;
if (h[to] >= mx)
{
sr = mx;
mx = h[to];
}
else sr = max(sr, h[to]);
}
up[v] = c;
for(auto to: g[v])
{
if (to == pr) continue;
if (h[to] == mx) dfs(to, v, max(c + 1, sr + 2));
else dfs(to, v, max(c + 1, mx + 2));
}
}
ll get_mx(int n)
{
DFS(0, 0);
dfs(0, 0, 0);
ll ans = 0;
for(int v = 0; v < n; v++)
{
vector < int > ve;
ve.pb(up[v]);
for(auto to: g[v])
{
if (to == pred[v]) continue;
ve.pb(h[to] + 1);
}
sort(ve.rbegin(), ve.rend());
while (sz(ve) > 3) ve.pop_back();
if (sz(ve) == 3)
{
// cerr << v + 1 << " " << ve[0] << " " << ve[1] << " " << ve[2] << endl;
ans = max(ans, 1ll * (ve[1] + ve[2]) * ve[0]);
ans = max(ans, 1ll * (ve[0] + ve[2]) * ve[1]);
ans = max(ans, 1ll * (ve[0] + ve[1]) * ve[2]);
}
}
return ans;
}
int calc(int a, int b, int n)
{
vector < int > pr(n);
for(int i = 0; i < n; i++)
ra[i] = -1;
ra[a] = 0;
queue < int > q;
q.push(a);
while (!q.empty())
{
int v = q.front();
q.pop();
for(auto to: g[v])
{
if (ra[to] == -1)
{
ra[to] = ra[v] + 1;
pr[to] = v;
q.push(to);
}
}
}
int mx = ra[b];
while (1)
{
ra[b] = 0;
q.push(b);
if (b == a) break;
b = pr[b];
}
for(int i = 0; i < n; i++)
if (ra[i] != 0) ra[i] = -1;
while (!q.empty())
{
int v = q.front();
q.pop();
for(auto to: g[v])
{
if (ra[to] == -1)
{
ra[to] = ra[v] + 1;
pr[to] = v;
q.push(to);
}
}
}
int cnt = 0;
for(int i = 0; i < n; i++)
cnt = max(cnt, ra[i]);
return cnt * mx;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif // LOCAL
int n;
cin >> n;
for(int i = 0; i < n - 1; i++)
{
int x, y;
cin >> x >> y;
x--; y--;
g[x].pb(y);
g[y].pb(x);
}
for(int i = 0; i < n; i++)
leaf[i] = (sz(g[i]) == 1);
ll mx = get_mx(n), k = 0;
for(int i = 0; i < n; i++)
{
if (!leaf[i]) continue;
for(int j = i + 1; j < n; j++)
{
if (!leaf[j]) continue;
int c = calc(i, j, n);
k += (c == mx);
}
}
cout << mx << " " << k;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23804 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23804 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23804 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23756 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23836 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
