P17141 [NOI 2026] 传送题解

:::info[Description] Link. :::

:::infoSolution 考虑固定终点 $y$ ，则容易发现最优策略一定存在一个距离阈值 $D$ 使得距离 $y$ 不超过 $D$ 的点直接沿着最短路走向 $y$ ，距离更远的点则需要使用传送门。设距离 $y$ 恰好为 $i$ 的点有 $c_i$ 个则如果传送直到落入前 $D$ 层再走向终点期望为 $C=\dfrac{n+\sum\limits_{i=0}^Dic_i}{\sum\limits_{i=0}^Dc_i}$ 。然后考虑是否应该继续把第 $D+1$ 层也改成走路只需要判是否有 $C>D+1$ 即可。移项一下可得 $\sum\limits_{i=0}^Dc_i(D-i+1)<n$ 。这个东西是有单调性的，因此第一次出现左边 $\ge n$ 的时候当前的 $D$ 值就是最优的。然后因为树上只要有第 $D$ 层存在就有 $c_0,c_1,\ldots,c_D\ge 1$ 因此有 $D=O(\sqrt n)$ 且常数很小。

然后考虑 dp。设 $f_{u,i}$ 表示距离 $u$ 点恰好为 $i$ 的点的数量，树上有 $f_{i,0}=1,f_{i,1}=\deg(i)$ 。然后可以直接递推得到 $f_{u,2}=\sum\limits_vf_{v,1}-\deg(u)f_{u,0},f_{u,i}=\sum\limits_vf_{v,i-1}-(\deg(u)-1)f_{u,d-2}$ ，转移只和最近的两层有关，因此只保存最近两层 dp 信息即可。

总时间复杂度为 $O(n\sqrt n)$ ，卡常后可以通过该题。 :::

:::success[Code]

// #include "teleport.h"
#include <bits/stdc++.h>
#include <cassert>
#include <ext/pb_ds/assoc_container.hpp>

std::vector<std::pair<long long, int>> teleport(int c, int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> x, std::vector<int> y);

constexpr int N = 500010;

int st[N][20], dep[N], fa[N];
std::vector<int> adj[N];
inline void dfs(int u, int p) {
    dep[u] = dep[p] + 1, st[u][0] = fa[u] = p;
    for (int &v : adj[u]) if (v != p) dfs(v, u);
}

inline int lca(int a, int b) {
    if (dep[a] < dep[b]) std::swap(a, b);
    int d = dep[a] - dep[b];
    for (int i = 19; ~i; --i) if (d >> i & 1) a = st[a][i];
    if (a == b) return a;
    for (int i = 19; ~i; --i) if (st[a][i] != st[b][i]) a = st[a][i], b = st[b][i];
    return st[a][0];
}

inline int dist(int a, int b) { return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }

std::pair<long long, int> oo[N];
int deg[N], s[N], q[N];
unsigned f[N], g[N], h[N];
long long ss[N];

std::vector<std::pair<long long, int>> teleport(int c, int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> x, std::vector<int> y) {
    for (int i = 0; i < n; ++i) deg[i] = 0;
    for (int i = 0; i < n - 1; ++i) {
        ++deg[u[i]], ++deg[v[i]];
        adj[u[i]].emplace_back(v[i]);
        adj[v[i]].emplace_back(u[i]);
    } dfs(0, 0);
    for (int i = 1; i < 20; ++i) for (int j = 0; j < n; ++j) st[j][i] = st[st[j][i - 1]][i - 1];
    unsigned *F = f, *G = g, *H = h;
    for (int i = 0; i < n; ++i) G[i] = 1, oo[i] = {0, 0}, F[i] = H[i] = s[i] = ss[i] = 0, q[i] = i;
    for (int d = 0, rem = n; rem; ++d) {
        int nr = 0;
        for (int j = 0; j < rem; ++j) {
            int i = q[j];
            s[i] += G[i], ss[i] += s[i];
            if (ss[i] >= n) {
                long long a = n + 1LL * (d + 1) * s[i] - ss[i];
                long long gg = std::gcd(a, (long long)s[i]);
                oo[i] = {a / gg, s[i] / gg};
            } else q[nr++] = i;
        } rem = nr;
        if (!rem) break;
        if (!d) for (int i = 0; i < n; ++i) H[i] = deg[i];
        else {
            for (int i = 0; i < n; ++i) H[i] = 0u - F[i] * (d == 1 ? deg[i] : deg[i] - 1);
            for (int i = 1; i < n; ++i) H[i] += G[fa[i]], H[fa[i]] += G[i];
        }
        std::swap(F, G);
        std::swap(G, H);
    } std::vector<std::pair<long long, int>> res;
    for (int i = 0; i < m; ++i) {
        auto [a, b] = oo[y[i]];
        int d = dist(x[i], y[i]);
        if (1LL * b * d < a) res.emplace_back(d, 1);
        else res.emplace_back(oo[y[i]]);
    } return res;
}

:::

难度：紫

鲜活指数：7

隐藏／恢复文章

随机文章

P17141 [NOI 2026] 传送 题解

随机文章

P17141 [NOI 2026] 传送题解