[NOIP 2016 提高组] 天天爱跑步 题解

· · 题解

对于一个观察点 u 在路径的位置进行讨论。

如果观察点 u 在一条路径的 s\to lca_{s,t} 上， 只有当 dep_s-dep_u=w_u 时才能观测到。把式子移项得到 dep_s=dep_u+w_u。

如果观察点 u 在一条路径的 lca_{s,t}\to t 上， 只有当 dep_u+dep_s-2dep_{lca_{s,t}}=w_u 是才能被观测到。移项得到 dep_s-2dep_{lca_{s,t}}=w_u-dep_u。

考虑对每个观察点 u 维护两个桶 t1,t2，里面分别存 dep_s 与 dep_s-2dep_{lca_{s,t}} 的出现次数。

那么观察点 u 的答案就是 t1_{dep_u+w_u}+t2_{w_u-dep_u}。

当然，肯定不能暴力枚举每一条路径上的观察点 u 去维护桶。

既然是路径，那么就考虑差分。

给 s 的桶的 dep_s 处加一， 给 fa_{lca_{s,t}} 的桶的 dep_s 处减一。

给 t 的桶的 dep_s-2dep_{lca_{s,t}} 处加一， 给 lca_{s,t} 的桶的 dep_s-2dep_{lca_{s,t}} 处减一。

然后，对于每个 u，让它合并所有儿子 v 的桶即可。

但是复杂度还是 O(n^2) 的，因为合并桶的复杂度是 O(n)。

那么考虑 dsu on tree 去维护桶即可。

最后复杂度是 O(n\log n)。

代码是很好写的。

#include <bits/stdc++.h>

void Freopen() {
    freopen("", "r", stdin);
    freopen("", "w", stdout);
}

using namespace std;
const int N = 3e5 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;

int n, m;
vector< int> G[N];

int w[N];

int siz[N], son[N], dep[N], fa[N];

void init1( int u, int fu) {
    siz[u] = 1, fa[u] = fu, dep[u] = dep[fu] + 1;

    for ( auto v : G[u]) {
        if (v == fu) continue ;
        init1(v, u);

        siz[u] += siz[v];
        son[u] = (siz[v] > siz[son[u]] ? v : son[u]);
    }
}

int tot;
int dfn[N], ed[N], rev[N], top[N];

void init2( int u, int topt) {
    dfn[u] = ++ tot, rev[dfn[u]] = u, top[u] = topt;

    if (son[u]) init2(son[u], topt);
    for ( auto v : G[u])
        if (v != fa[u] && v != son[u])
            init2(v, v);

    ed[u] = tot;
}

int lca( int u, int v) {
    int tu = top[u], tv = top[v];
    while (tu != tv) {
        if (dep[tu] < dep[tv]) swap(u, v), swap(tu, tv);
        u = fa[tu], tu = top[u];
    }

    return (dep[u] < dep[v] ? u : v);
}

vector< pair< int, int> > vec1[N], vec2[N];
int ans[N], t1[3 * N], t2[3 * N];

#define py 300000

void dfs( int u, int op) {
    for ( auto v : G[u])
        if (v != fa[u] && v != son[u]) dfs(v, 0);
    if (son[u]) dfs(son[u], 1);

    for ( auto p : vec1[u])
        t1[p.first + py] += p.second;

    for ( auto p : vec2[u])
        t2[p.first + py] += p.second;

    for ( auto v : G[u])
        if (v != fa[u] && v != son[u])
            for ( int i = dfn[v]; i <= ed[v]; i ++) {
                for ( auto p : vec1[rev[i]])
                    t1[p.first + py] += p.second;

                for ( auto p : vec2[rev[i]])
                    t2[p.first + py] += p.second;              
            }

    ans[u] = t1[dep[u] + w[u] + py] + t2[w[u] - dep[u] + py];

    if (! op) 
        for ( int i = dfn[u]; i <= ed[u]; i ++) {
            for ( auto p : vec1[rev[i]])
                t1[p.first + py] -= p.second;

            for ( auto p : vec2[rev[i]])
                t2[p.first + py] -= p.second;  
        }
}

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

    cin >> n >> m;

    for ( int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }

    init1(1, 0), init2(1, 1);

    for ( int i = 1; i <= n; i ++) cin >> w[i];

    while (m --) {
        int s, t; cin >> s >> t;
        int l = lca(s, t);

        vec1[s].push_back({dep[s], 1});
        vec1[fa[l]].push_back({dep[s], -1});
        vec2[t].push_back({dep[s] - 2 * dep[l], 1});
        vec2[l].push_back({dep[s] - 2 * dep[l], -1});
    }

    dfs(1, 1);

    for ( int i = 1; i <= n; i ++) cout << ans[i] << ' ';

    return 0;
}