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;
}