题解：P15947 [JOI Final 2026] 集邮 5 / Collecting Stamps 5

_IceCream_ · 2026-11-11 09:04:57 · 题解

为啥题解区一堆 \log^2 写法？这题不是轻松单 \log 吗。

Content

有一棵 n 个节点的树，带点权 T_i。你需要对每个点 u 求出，有多少个点 v 满足：从 u 到 v 的路径上存在一个点 x 满足 \operatorname{dist}(u, x) \ge T_x，且 \operatorname{dist}(u, v) \le D。

Solution

看到 \operatorname{dist}(u, v) \le D 这种邻域形式，很难不想到点分治。

然后这个至少一个点的限制有点奇怪，我们可以反着做，大条件仍然是 \operatorname{dist}(u, v) \le D，但是我们去统计没有任意一个点满足限制的条件，也就是 \forall x, \operatorname{dist}(u, x) \lt T_x。

然后我们把它放到点分治下讨论，对于经过根 rt 的路径 (u, v) 来说，这个限制分为两种情况。

Case 1 u 到 rt

如果点 x 在 u 到 rt 的路径上，它不满足条件当且仅当 dep_u - dep_x \lt T_x，即 dep_u \lt T_x + dep_x。

这里我们可以对 T_x + dep_x 取最小值，因为这是一个充要条件，如果 dep_u 连最小值都满足不了，其它的值肯定更满足不了了。

所以我们记 B_x 表示从 rt 到 x 这条路径上，T_x + dep_x 的最小值，可以递推，即 B_x = \min (B_{fa}, T_x + dep_x)。

那么 u 不合法当且仅当 dep_u \lt B_u。

Case 2 rt 到 v

如果点 x 在 rt 到 v 的路径上，它不满足条件当且仅当 dep_u + dep_x \lt T_x，即 dep_u \lt T_x - dep_x。

同样的，我们对 T_x - dep_x 取最小值，维护一个 C_x 表示从 rt 到 x 这条路径上，T_x - dep_x 的最小值，同样可以递推，C_x = \min (C_{fa}, T_x - dep_x)。

我们综合起来，我们要统计的一个过 rt 的路径 u, v 不合法当且仅当 dep_u \lt B_u, dep_u \lt C_v, dep_u + dep_v \le D。

我们发现，后两个条件跟 u, v 都有关，且符号相同，我们可以合并一下，取 L_v = \min (C_v - 1, D - dep_v)，条件就变成了 dep_u \lt B_u, dep_u \le L_v。

走到这一步，实际上这题可以用一个二维偏序做，复杂度是 O(n \log^2 n)，但是根本没必要啊。

我们对 L_v 开一个桶 cnt_i 表示 L_v = i 的 v 有多少个，然后对它做一个后缀和，此时 cnt_i 表示 L_v \ge i 的 v 有多少个。然后去遍历 u，判断它是不是满足 dep_u \lt B_u，如果满足就直接加入答案 cnt_{dep_u} 不就做完了吗。

然后是统计 dep_u + dep_v \le D，这个不一样的吗。开一个深度桶 cntd_i 记有多少个 u 满足 dep_u = i，然后做前缀和，查询 D - dep_v 就可以了。

记得对子树做容斥，因为我们上述提到的所有思路都没有排除 u, v 在同一子树内的情况，如果在同一子树内，它就不会经过 rt，上述的计数也是不成立的。

复杂度是优美的 O(n \log n)，挺好写。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;

bool ST;

const int N = 4e5 + 5;
int n, D, a[N];
struct Edge { int v, nxt; } e[N << 1];
int ecnt, head[N];
void addEdge (int u, int v) {
    e[++ecnt] = {v, head[u]};
    head[u] = ecnt;
}

int siz[N], rt, dp[N], S;
bool vis[N];

void getroot (int u, int fa) {
    siz[u] = 1, dp[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        getroot (v, u);
        siz[u] += siz[v];
        dp[u] = max (dp[u], siz[v]);
    }
    dp[u] = max (dp[u], S - siz[u]);
    if (dp[u] < dp[rt]) rt = u;
}

int dep[N], b[N], c[N], l[N];
int mxd, tot, dot[N];
void getinfo (int u, int fa) {
    dot[++tot] = u;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        dep[v] = dep[u] + 1; mxd = max (mxd, dep[v]);
        b[v] = min (b[u], a[v] + dep[v]);
        c[v] = min (c[u], a[v] - dep[v]);
        l[v] = min (c[v] - 1, D - dep[v]);
        getinfo (v, u);
    }
}

int cnt[N], cntd[N], bad[N], totl[N];
// 我们这里可以封装一下，opt = -1 就是对子树做容斥。
void calc (int u, int opt) {
    tot = 0;
    mxd = dep[u];
    if (opt != -1) {
        // 特别注意这里对子树做容斥的时候，我们要用的是以 u 为根的信息，所以这里不能重复统计以 v 为根的信息
        dep[u] = 0;
        b[u] = a[u] + dep[u];
        c[u] = a[u] - dep[u];
        l[u] = min (c[u] - 1, D - dep[u]);
    }
    getinfo (u, 0);
    for (int i = 1; i <= tot; ++i) (l[dot[i]] >= 0) && (cnt[min (mxd, l[dot[i]])]++), cntd[dep[dot[i]]]++;
    for (int i = mxd - 1; i >= 0; --i) cnt[i] += cnt[i + 1];
    for (int i = 1; i <= mxd; ++i) cntd[i] += cntd[i - 1];
    for (int i = 1; i <= tot; ++i) {
        if (dep[dot[i]] < b[dot[i]]) bad[dot[i]] += opt * cnt[dep[dot[i]]];
        if (D - dep[dot[i]] >= 0) totl[dot[i]] += opt * cntd[min (mxd, D - dep[dot[i]])];
    }
    for (int i = 0; i <= mxd; ++i) cnt[i] = cntd[i] = 0;
}

void solve (int u) {
    vis[u] = true;
    calc (u, 1);
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (vis[v]) continue;
        calc (v, -1);
    }
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (vis[v]) continue;
        S = siz[v], rt = 0; dp[0] = n;
        getroot (v, u);
        solve (rt);
    }
}

bool ED;

int main () {

    ios::sync_with_stdio (false);
    cin.tie (0), cout.tie (0);

    cerr << "[Memory] " << (&ST - &ED) / 1024 / 1024 << " MB\n";

    // freopen (".in", "r", stdin);
    // freopen (".out", "w", stdout);

    cin >> n >> D;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        addEdge (u, v);
        addEdge (v, u);
    }
    S = dp[0] = n, rt = 0;
    getroot (1, 0);
    solve (rt);
    for (int i = 1; i <= n; ++i) cout << totl[i] - bad[i] << '\n';

    return 0;
}

::::