# FULL

unknown
c_cpp
2 years ago
6.7 kB
1
Indexable
Never
```        diam_parent[v] = diam_parent[p];
for (auto to : g[v])
{
if (in_DIAM[to] || to == p)
continue;
dfs(to, v);
}
}
void calc_self(int v, int p, int k = 0)
{
sz[v] = 1;
self_val[v] = max(self_val[v], dp[v].diam);
self_val[v] = max(self_val[v], k);
k_max maxs = k_max(2), kek = k_max(3);
for (auto to : g[v])
{
if (in_DIAM[to] || to == p)
continue;
}
for (auto to : g[v])
{
if (in_DIAM[to] || to == p)
continue;
int kk = k;
kk = max(kk, maxs.get({to}));
kk = max(kk, kek.get({to}, 2));
calc_self(to, v, kk);
sz[v] += sz[to];
}
}
void calc_left(int v, int p, int k)
{
left_val[v] = max(self_val[v], k);
for (auto to : g[v])
{
if (in_DIAM[to] || to == p)
continue;
calc_left(to, v, k);
}
}

void calc_right(int v, int p, int k)
{
right_val[v] = max(self_val[v], k);
for (auto to : g[v])
{
if (in_DIAM[to] || to == p)
continue;
calc_right(to, v, k);
}
}
vector<ll> solve(int _n, vector<pii> edges, vector<pii> queries)
{
n = _n;
for (auto edge : edges)
{
int v = edge.f;
int u = edge.s;
g[v].pb(u);
g[u].pb(v);
}
A = get_farthest(1, 1);
B = get_farthest(A, A);
for (int v = B; v != A; v = parent[v])
DIAM.pb(v);
DIAM.pb(A);
for (int i = 0; i < DIAM.size(); i++)
{
int v = DIAM[i];
in_DIAM[v] = 1;
in_DIAM_pos[v] = i;
}

for (int i = 0; i < DIAM.size(); i++)
{
int v = DIAM[i];
dfs(v, v);
calc_self(v, v);
}
for (int i = 0, farthest = 0; i < DIAM.size(); i++)
{
int v = DIAM[i];
int prev = 0;
left_val[v] = max(left_val[v], self_val[v]);
if (i)
{
prev = left_val[DIAM[i - 1]];
farthest = farthest + 1;
left_val[v] = max(left_val[v], prev);
left_val[v] = max(left_val[v], farthest + dp[v].farthest);
}
k_max maxs = k_max(2);
for (auto to : g[v])
{
if (in_DIAM[to])
continue;
}
for (auto to : g[v])
{
if (in_DIAM[to])
continue;
calc_left(to, v, max(prev, farthest + maxs.get({to})));
}
farthest = max(farthest, dp[v].farthest);
}

for (int i = DIAM.size() - 1, farthest = 0; i >= 0; i--)
{
int v = DIAM[i];
int prev = 0;
right_val[v] = max(right_val[v], self_val[v]);
if (i + 1 < DIAM.size())
{
prev = right_val[DIAM[i + 1]];
farthest = farthest + 1;
right_val[v] = max(right_val[v], prev);
right_val[v] = max(right_val[v], farthest + dp[v].farthest);
}
k_max maxs = k_max(2);
for (auto to : g[v])
{
if (in_DIAM[to])
continue;
}
for (auto to : g[v])
{
if (in_DIAM[to])
continue;
calc_right(to, v, max(prev, farthest + maxs.get({to})));
}
farthest = max(farthest, dp[v].farthest);
}

fen lefts, rights;
for (int i = 1; i <= n; i++)
{
int pos = in_DIAM_pos[diam_parent[i]];
lefts.inc(pos, 1);
rights.inc(pos, 1);
events[m++] = {left_val[i], {0, i}};
events[m++] = {right_val[i], {1, i}};
}
for (int i = 0; i < DIAM.size(); i++)
{
int v = DIAM[i];
events[m++] = {self_val[v], {2, v}};
}
sort(events, events + m);
reverse(events, events + m);

set<int> blocked;
blocked.insert(0);
blocked.insert(DIAM.size() - 1);

for (int i = 0; i < m; i++)
{
int val = events[i].f;
int type = events[i].s.f;
int pos = in_DIAM_pos[diam_parent[events[i].s.s]];
if (type == 0)
{
int l = pos + 1;
int r = (*blocked.upper_bound(pos));
ans[val] += rights.get(l, r);
lefts.inc(pos, -1);
}
if (type == 1)
{
int l = (*(--blocked.lower_bound(pos)));
int r = pos - 1;
ans[val] += lefts.get(l, r);
rights.inc(pos, -1);
}
if (type == 2)
{
int l = (*(--blocked.lower_bound(pos)));
int r = (*blocked.upper_bound(pos));
ans[val] += lefts.get(l, pos - 1) * rights.get(pos + 1, r);
blocked.insert(pos);
}
}
for (auto v : DIAM)
ans[DIAM.size() - 1] += 1ll * sz[v] * (sz[v] - 1) / 2;

k_max selfs = k_max(3);
for (auto v : DIAM)

vector<ll> result;

for (auto query : queries)
{
if (query.f > 0)
{
int v = query.f;
int u = query.s;
int val = 0;
if (diam_parent[v] == diam_parent[u])
val = max(val, (int)DIAM.size() - 1);
if (in_DIAM_pos[diam_parent[v]] > in_DIAM_pos[diam_parent[u]])
swap(v, u);
val = max(val, left_val[v]);
val = max(val, right_val[u]);
val = max(val, selfs.get({diam_parent[u], diam_parent[v]}));
result.pb(val);
}
else
{
int k = query.s;
result.pb(ans[k]);
}
}
return result;
}
int main()
{
int n, m;
vector<pii> edges;
vector<pii> queries;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int v, u;
scanf("%d%d", &v, &u);
edges.pb({v, u});
}
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
int type;
scanf("%d", &type);
if (type == 1)
{
int v, u;
scanf("%d%d", &v, &u);
queries.pb({v, u});
}
else
{
int k;
scanf("%lld", &k);
queries.pb({0, k});
}
}
vector<ll> ans = solve(n, edges, queries);
for (auto val : ans)
printf("%lld\n", val);
return 0;
}```