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

题目描述

传送门！！！ 挺难的这个题，基本上说是没思路。简单来说，给定一棵树，告诉你第 $i$ 个玩家的出发点和终点，这个玩家会沿着树上最短路移动，每秒移动一条边的距离。给定每个结点的观测时间，如果在观测时间有人经过，输出每个点经过的人数。

思路解析

赛场上作为蒟蒻的我，当然是没想到正解的啦。瞄准 $1$ , $4$ 数据点，使用 unordered_map 特判即可。第 $5$ 个点没试过，也许暴力能过？
考虑正解：我们其实就是想对树上最短路进行计数，也就是维护树上区间加法操作。没错差分秒了！那么在什么地方差分呢？ 这里作者也是过于懒惰了！直接上图，感谢董晓老师的题解。再次%%% + orz。注意，我们在每一个结点都建立一棵权值线段树，用 $sum$ 维护区间出现次数和。
接着，我们使用线段树合并操作统计次数。
这里只做关键位置的解释： 首先在 dfs3 函数中，我们遍历了每一个结点，如果来到叶子结点与上方空间足够，那么查询映射位置。不管如何，都要向下查询。 其次，下面为四次差分操作，第一个参数为修改位置。

完整代码

#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define inc(i, l, r) for(long long i = l; i <= r; i++)
#define dec(i, l, r) for(long long i = l; i >= r; i--)
//使用蔡氏秘法：我不道啊？我网上下载下来的！
using namespace std;
const long long maxn = 299998 + 5;
long long n, m, w[maxn];
vector < long long > G[maxn];
long long depth[maxn], son[maxn], father[maxn], siz[maxn];
void dfs1(long long now, long long fa) {//我绝对不会让你知道，我是因为倍增太难记了所以打的树剖
    depth[now] = depth[fa] + 1, father[now] = fa, siz[now] = 1;
    for(long long v : G[now]) {
        if(v == fa) continue;
        dfs1(v, now);
        siz[now] += siz[v];
        if(siz[v] > siz[son[now]]) son[now] = v;
    }
}
long long top[maxn], id[maxn], rk[maxn], num;
void dfs2(long long now, long long Tp, long long fa) {
    top[now] = Tp, id[now] = ++num, rk[num] = now;
    if(son[now]) dfs2(son[now], Tp, now);
    for(long long v : G[now]) {
        if(v == fa || v == son[now]) continue;
        dfs2(v, v, now);
    }
}
long long lca(long long u, long long v) {
    while(top[u] != top[v]) {
        if(depth[top[u]] < depth[top[v]]) swap(u, v);
        u = father[top[u]];
    }
    return depth[u] < depth[v] ? u : v;
}

long long ls[maxn * 55], rs[maxn * 55], sum[maxn * 55], tot;
long long root[maxn], ans[maxn];

void change(long long &u, long long l, long long r, long long p, long long k) {//单点修改
    if(!u) u = ++tot;
    if(l == r) {
        sum[u] += k;
        return;
    }
    long long mid = (l + r) >> 1;
    if(p <= mid) change(ls[u], l, mid, p, k);
    else change(rs[u], mid + 1, r, p, k);
}
long long merge(long long x, long long y, long long l, long long r) {
    //合并
    if(!x || !y) return x + y;
    if(l == r) {
        sum[x] += sum[y];
        return x;
    }
    long long mid = (l + r) >> 1;
    ls[x] = merge(ls[x], ls[y], l, mid);
    rs[x] = merge(rs[x], rs[y], mid + 1, r);
    return x;
}
long long query(long long u, long long l, long long r, long long p) { //单点查询
    if(l == r) {
        return sum[u];
    }
    long long mid = (l + r) >> 1;
    if(p <= mid) return query(ls[u], l, mid, p);
    if(p > mid) return query(rs[u], mid + 1, r, p);
}
void dfs3(long long x, long long fa) {
    for(long long y : G[x]) {
        if(y == fa) continue;
        dfs3(y, x);
        root[x] = merge(root[x], root[y], 1, n << 1);
    }
    if(w[x] && n + depth[x] + w[x] <= n << 1) {
        ans[x] += query(root[x], 1, n << 1, n + depth[x] + w[x]);
    }
    ans[x] += query(root[x], 1, n << 1, n + depth[x] - w[x]);
}
int main(){
	cin >> n >> m;
    inc(i, 1, n - 1) {
        long long u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1, 0);
    inc(i, 1, n) cin >> w[i];
    inc(i, 1, m) {
        long long x, y;
        cin >> x >> y;
        long long l = lca(x, y);
        change(root[x], 1, n << 1, n + depth[x], 1);
        change(root[y], 1, n << 1, n + 2 * depth[l] - depth[x], 1);
        change(root[l], 1, n << 1, n + depth[x], -1);
        change(root[father[l]], 1, n << 1, n + 2 * depth[l] - depth[x], -1);
    }
    dfs3(1, 0);
    inc(i, 1, n) cout << ans[i] << " ";
	return 0;
}