#include <stdio.h>
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = (int)1e6 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;
void megaRandom() {
unsigned int FOR;
asm("rdtsc" : "=A"(FOR));
srand(FOR);
}
int n;
vector<int> g[N];
int down[N], u[N];
int up[25][N], tin[N], tout[N], timer;
int ver[N];
int dist[N];
void dfs(int x, int pr = 0) {
tin[x] = ++ timer;
up[0][x] = pr;
for(int i = 1; i <= 20; i ++)
up[i][x] = up[i - 1][x];
ver[timer] = x;
for(auto to : g[x]) {
if(to == pr)
continue;
dist[to] = dist[x] + 1;
dfs(to, x);
down[x] = max(down[x], down[to] + 1);
}
tout[x] = timer;
}
bool is_par(int x, int y) {
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
int lca(int x, int y) {
if(is_par(x, y)) return x;
if(is_par(y, x)) return y;
int v = x;
for(int i = 20; i >= 0; i --)
if(up[i][v] > 0 && !is_par(up[i][v], y))
v = up[i][v];
return up[0][v];
}
void calc_u(int x, int pr = 0) {
int mx1 = 0, mx2 = 0;
for(auto to : g[x]) {
if(to == pr)
continue;
if(down[to] > mx1)
mx2 = mx1, mx1 = down[to];
else
mx2 = max(mx2, down[to]);
}
for(auto to : g[x]) {
if(to == pr)
continue;
u[to] = max(u[to], u[x] + 1);
if(mx1 == down[to])
u[to] = max(u[to], mx2 + 2);
else
u[to] = max(u[to], mx1 + 2);
}
for(auto to : g[x]) {
if(to == pr)
continue;
calc_u(to, x);
}
}
vector<int> leaf;
int main() {
megaRandom();
//freopen("road.in", "r", stdin);
//freopen("road.out", "w", stdout);
cin >> n;
for(int i = 1, x, y; i < n; i ++) {
cin >> x >> y;
g[x].pb(y), g[y].pb(x);
}
if(n == 2) {
cout << "0 1";
return 0;
}
int start = 1;
for(int i = 1; i <= n; i ++) {
if(sz(g[i]) != 1) {
start = i;
break;
}
}
dfs(start);
calc_u(start);
//cout << "start: " << start << "\n";
for(int i = 1; i <= n; i ++) {
//cout << "i: " << i << " up: " << u[i] << "\n";
int x = ver[i];
if(sz(g[x]) == 1)
leaf.pb(x);
}
int mx = 0, mx_cnt = 0;
for(int i = 0; i < sz(leaf); i ++) {
int prv = -1, cur = 0, l = i - 1, r = i + 1, temp = 0, what = 0;
for(int j = i + 1; j < sz(leaf); j ++) {
int _lca = lca(leaf[i], leaf[j]), tempo = 0;
while(l >= 0 && is_par(_lca, lca(leaf[l], leaf[l + 1]))) {
cur = max(cur, dist[leaf[l]] - dist[lca(leaf[l], leaf[l + 1])]);
l --;
}
while(r < sz(leaf) && is_par(_lca, lca(leaf[r], leaf[r - 1]))) {
tempo = max(tempo, dist[leaf[r]] - dist[lca(leaf[r], leaf[r - 1])]);
r ++;
}
if(prv == _lca)
what = max(what, dist[leaf[j - 1]] - dist[lca(leaf[j - 1], leaf[j])]);
if(prv != -1 && prv != _lca)
cur = max(cur, temp), what = 0;
//cout << leaf[i] << ' ' << leaf[j] << " cur: " << max({cur, u[_lca], tempo, what}) << " lca: " << _lca << "\n";
if(max({tempo, cur, u[_lca], what}) * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) == mx)
mx_cnt ++;
if(max({tempo, cur, u[_lca], what}) * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) > mx)
mx = max({tempo, cur, u[_lca], what}) * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]), mx_cnt = 1;
prv = _lca;
temp = max(temp, dist[leaf[j]] - dist[_lca]);
}
}
cout << mx << ' ' << mx_cnt;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
146568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
146568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
146568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
