热门标签
更多>
搜索结果
查询Tags标签： HNOI2015，共有 3条记录-
P3242 [HNOI2015] 接水果
P3242 [HNOI2015] 接水果 整体二分练手题。 考虑一条路径 \((x,y)\) 被另一条路径 \((u,v)\) 包含的本质。 考虑 dfs 序，设 \(st_x=dfn_x\)，$$ed_x=dfn_x+siz_x-1$。 不妨设 \(st_x<st_y\)。\(\operatorname{LCA}(x,y)=x\) 则 \(u\in [1,st_z-1]\) 或 \(u \in[ed_z+1…
2022/6/2 23:24:16 人评论 次浏览 -
luogu P3241 [HNOI2015]开店
题面传送门 看到这种东西想到差分，即差分成\([1,r]\)减去\([1,l]\)的答案。 距离的式子其实是\(dist_u+dist_v-2*dist_{lca(u,v)}\)前面两项平凡所以要求\(dist_{lca(u,v)}\) 然后这个有经典套路就是每个点往根加和查就是这个式子，直接树剖就好了。 因为强制在线所以可持…
2021/8/3 23:06:12 人评论 次浏览 -
luogu P3241 [HNOI2015]开店
题面传送门 看到这种东西想到差分，即差分成\([1,r]\)减去\([1,l]\)的答案。 距离的式子其实是\(dist_u+dist_v-2*dist_{lca(u,v)}\)前面两项平凡所以要求\(dist_{lca(u,v)}\) 然后这个有经典套路就是每个点往根加和查就是这个式子，直接树剖就好了。 因为强制在线所以可持…
2021/8/3 23:06:12 人评论 次浏览
