Description

题目链接

Solution

听说是 NOIp 史上最毒瘤的题之一了...把这题放在 d1t2,CCF 也是可以的。不过部分分还是挺多的。

接下来设 $d_x$ 表示 $x$ 的深度。

对于 $s_i = t_i$ 的测试点,只需要把这个点答案加 $1$ 即可。

对于 $w_i = 0$ 的测试点,只需要看有多少 $s_i$ 在这个点上即可。

然后这个点是暴力分。

考虑链上的情况:处在 $i$ 的人只能往左走或者往右走。我们只考虑往右走的情况,那么能产生贡献的点 $j$ 必须满足 $w_j = j - i$,即 $i = j - w_j$。

设置一个桶 $t_i$,做一次差分,将每条路径的起点 $+1$,终点 $-1$,之后点 $i$ 的答案为 $t_{i + w_i} + t_{i - w_i}$。

对于 $s_i = 1$,现在有观察员 $i$ 和玩家 $j$,不难发现只有当 $d_i = w_i$ 且 $j$ 在 $i$ 的子树内时才会有贡献。dfs 一遍树统计答案即可。

对于 $t_i = 1$,跟上一种情况类似,产生贡献的条件为 $d_i + w_i = d_j$,且 $j$ 在 $i$ 的子树内。

接下来考虑正解。$s_i = 1$ 和 $t_i = 1$ 的情况已经给了我们很多启示,考虑将一条路线差分成 $u \rightarrow \operatorname{LCA}(u, v)$ 和 $\operatorname{LCA}(u, v) \rightarrow v$ 两条路线,且能对某观察员产生贡献的点一定在这个观察员的子树内,这样我们可以用一遍 dfs 统计答案。

对于每个玩家,预处理出 LCA 和路线距离。开两个桶 $t_1, t_2$,分别表示起点和终点所做的贡献。遍历 $x$ 的子树后统计 $t_1$ 和 $t_2$ 的差值作为 $x$ 这个点的答案,之后删去经过 LCA 的路径的贡献。最后特判一下 LCA 如果也产生贡献就将答案 $-1$。

其实树上差分的思想比较难想到,俗话说智商不够数据结构来凑,这道题可以对每个点建立线段树然后线段树合并,比这种方法好想的多,但是我数据结构实在差,所以就算了。我看题解还有主席树的。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

const int maxn = 3e5 + 10, maxm = 3e5 + 10;

struct Edge {
    int u, v, lca, dis;
} a[maxm];

std::vector<int> g[maxn], g1[maxn], g2[maxn];
int siz[maxn], son[maxn], fa[maxn], dfn[maxn], top[maxn], dep[maxn], w[maxn], ans[maxn], t[maxn], t1[maxn * 2], t2[maxn * 2];
int n, m, cnt;

void dfs1(int x, int p) {
    dep[x] = dep[p] + 1;
    fa[x] = p;
    siz[x] = 1;
    for (auto i : g[x]) {
        if (i != p) {
            dfs1(i, x);
            siz[x] += siz[i];
            if (siz[i] > siz[son[x]])    son[x] = i;
        }
    }
}

void dfs2(int x, int tp) {
    dfn[x] = ++cnt;
    top[x] = tp;
    if (son[x]) {
        dfs2(son[x], tp);
        for (auto i : g[x]) {
            if (i != fa[x] && i != son[x]) {
                dfs2(i, i);
            }
        }
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]])    u = fa[top[u]];
        else    v = fa[top[v]];
    }
    return dep[u] < dep[v] ? u : v;
}

void solve(int x, int p) {
    int s1 = t1[w[x] + dep[x]], s2 = t2[w[x] - dep[x] + maxn];
    for (auto i : g[x]) {
        if (i != p) {
            solve(i, x);
        }
    }
    t1[dep[x]] += t[x];
    for (auto i : g1[x])    ++t2[a[i].dis - dep[a[i].v] + maxn];
    ans[x] += t1[w[x] + dep[x]] - s1 + t2[w[x] - dep[x] + maxn] - s2;
    for (auto i : g2[x]) {
        --t1[dep[a[i].u]];
        --t2[a[i].dis - dep[a[i].v] + maxn];
    }
}

int main() {
    read(n), read(m);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i <= n; ++i)    read(w[i]);
    for (int i = 1; i <= m; ++i) {
        read(a[i].u), read(a[i].v);
        a[i].lca = lca(a[i].u, a[i].v);
        a[i].dis = dep[a[i].u] + dep[a[i].v] - 2 * dep[a[i].lca];
        ++t[a[i].u];
        g1[a[i].v].push_back(i);
        g2[a[i].lca].push_back(i);
        if (dep[a[i].lca] + w[a[i].lca] == dep[a[i].u])    --ans[a[i].lca];
    }
    solve(1, 0);
    for (int i = 1; i <= n; ++i)    printf("%d ", ans[i]);
    puts("");
    return 0;
}
Last modification:September 2nd, 2021 at 02:02 am