其实是个套路题? 近三年 NOIP 数据结构题 23 达成 √
考虑一位从 u 到 v 的玩家,令 lca=LCA(u,v)。
再设 depu 表示 u 的深度,fau 表示 u 的父亲。
那么考虑一个在 (u,lca) 路径上的点 p,若它能观察到 p,则一定有 depu−depp=Wp。
移项得 depu=Wp+depp。
再考虑一个在 (lca,v) 路径上的点 p,若它能观察到 p,则有 depu+depp−2deplca=Wp。
移项得 depu−2deplca=Wp−depp。
则,对于任意点 p 的观察员,若其可以观察到一个从 u 到 v 的玩家,则一定满足: 1. 其在 (u,v) 路径上。 2. depu=Wp+depp 或 depu−2deplca=Wp−depp。
则对于每个点的贡献,可以用树上差分来维护,注意 lca 处的细节判断。
线段树合并即可(虽然其实不需要)。
代码:
1 |
|