题解：P17141 [NOI 2026] 传送

· · 题解

思路还是比较清楚的，但是我怎么不会写点分树了。

如果我们已经蠕动了一段了再跳一下肯定前面的都白搭，所以策略一定是选择一个含 y 的有根连通块 S，里面的点直接爬，外面的点就随机跳。

对于 S 内的点 x，它爬到 y 的步数就是深度 d_x=\text{dis}(x,y)；而所有 S 外的点的期望是相等的，设其为 E，那么有：

E=\dfrac1n\left(\sum_{x\in S}d_x+(n-|S|)E\right)+1

解得 E=\dfrac1{|S|}\left(\displaystyle\sum_{x\in S}d_x+n\right)，要让它最小，一定是将 d_x 升序排序后选择一段前缀；而加入一个深度为 D 的点后，有 -\Delta E=\dfrac{1}{|S|(|S|+1)}\left(\displaystyle\sum_{x\in S}(d_x-D)+n\right)，可以发现如果选择一个 D 是优的，就会一直把这个深度取完，也就是说选择的恰好是所有距离 y 不超过某个距离 p_y 的所有点。

猜测 E 是单谷的，证明是容易的，那么就可以三分 E；或者可以发现 \Delta E 是单调的，也就是说 E 是凸的，二分 \Delta E，每次用点分树查，可以做到 \mathcal O(n\log^2 n+q)，使用毛毛虫火箭可以去掉一个 \log。

其实有更牛的做法，注意到对于相邻两个点 (u,v)，一定有 |p_u-p_v|\le1，不然就可以从小的一方拓展一步得到更优的取值，因此只需要对一个点二分（甚至不需要？），然后对于其它点 DFS 下去求 p 即可，只需要 \mathcal O(n) 次邻域询问，复杂度为 \mathcal O(n\log n+q)。

代码实现的细节非常多且恶心。

#include <bits/stdc++.h>
#include "teleport.h"
using namespace std;
#define il inline
typedef long long ll; typedef __int128 lll; typedef pair<ll, ll> pll;
const int N = 5e5 + 5;
int n, tot, dfn[N], dep[N], st[19][N], fa[N], siz[N], D[N]; pll E[N]; bool del[N]; vector<int> G[N];
void dfs(int u, int f) { dep[u] = dep[st[0][dfn[u] = ++tot] = f] + 1; for (int v : G[u]) if (v ^ f) dfs(v, u); }
il int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
il int lca(int x, int y) { if (x == y) return x; if ((x = dfn[x]) > (y = dfn[y])) swap(x, y); int d = __lg(y - x++); return get(st[d][x], st[d][y - (1 << d) + 1]); }
il int dis(int x, int y) { return dep[x] + dep[y] - (dep[lca(x, y)] << 1); }
void gsiz(int u, int f) { siz[u] = 1; for (int v : G[u]) if (v != f && !del[v]) gsiz(v, u), siz[u] += siz[v]; }
int  gcen(int u, int f, int n) { for (int v : G[u]) if (v != f && !del[v] && siz[v] << 1 > n) return gcen(v, u, n); return u; }
vector<int> c[N][2]; vector<ll> s[N][2];
void upd(int u, int f, int d, int p, bool tp) {
    if (d >= c[p][tp].size()) c[p][tp].resize(d + 1), s[p][tp].resize(d + 1);
    c[p][tp][d]++, s[p][tp][d] += d;
    for (int v : G[u]) if (v != f && !del[v]) upd(v, u, tp ? dis(v, fa[p]) : d + 1, p, tp);
}
void build(int u, int f) {
    gsiz(u, -1); int p = gcen(u, -1, siz[u]); fa[p] = f, del[p] = 1;
    upd(p, -1, 0, p, 0); if (~f) upd(p, -1, dis(p, f), p, 1);
    for (int v : G[p]) if (!del[v]) build(v, p);
}
il pll qry(int u, int D) {
    ll ct = 0, st = n;
    for (int x = u, f = -1; ~x; f = x, x = fa[x]) {
        int d = dis(x, u); if (D < d) continue;
        int p = min((int)c[x][0].size() - 1, D - d); ct += c[x][0][p], st += s[x][0][p] + (ll)c[x][0][p] * d;
        if (~f) p = min((int)c[f][1].size() - 1, D - d), ct -= c[f][1][p], st -= s[f][1][p] + (ll)c[f][1][p] * d;
    }
    return {st, ct};
}
il bool cmpl (const pll &a, const pll &b) { return (lll)a.first * b.second <  (lll)a.second * b.first; }
il bool cmplq(const pll &a, const pll &b) { return (lll)a.first * b.second <= (lll)a.second * b.first; }
void Dfs(int u, int f) {
    for (int v : G[u]) if (v ^ f) {
        int cd = D[u];
        while (cd > 0 && cmplq(qry(v, cd - 1), qry(v, cd))) cd--;
        while (cd < n - 1 && cmpl(qry(v, cd + 1), qry(v, cd))) cd++;
        E[v] = qry(v, D[v] = cd), Dfs(v, u);
    }
}
vector<pair<ll, int> > teleport(int _, int n, int m, vector<int> u, vector<int> v, vector<int> x, vector<int> y) {
    for (int i = 0; i < n - 1; i++) G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]);
    ::n = n, dfs(0, 0);
    for (int i = 1; 1 << i <= n; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++) st[i][j] = get(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
    build(0, -1);
    for (int i = 0; i < n; i++) for (int o : {0, 1}) for (int j = 1, l = c[i][o].size(); j < l; j++) c[i][o][j] += c[i][o][j - 1], s[i][o][j] += s[i][o][j - 1];
    int cd = 0; while (cd < n - 1 && cmpl(qry(0, cd + 1), qry(0, cd))) cd++;
    E[0] = qry(0, D[0] = cd), Dfs(0, -1);
    vector<pair<ll, int> > ans(m);
    for (int i = 0; i < m; i++) {
        int d = dis(x[i], y[i]); auto e = E[y[i]];
        if ((lll)d * e.second <= e.first) ans[i] = {d, 1};
        else { ll g = __gcd(e.first, e.second); ans[i] = {e.first / g, int(e.second / g)}; }
    }
    return ans;
}