BZOJ 5121 [2017 国家集训队测试]Hello world!

发布于 2017-12-12  255 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5121

题意:

一棵树,有点权,支持两个操作:

  1. 从 s 到 t 每隔 k 个位置都开个方。
  2. 从 s 到 t 每隔 k 个位置加起来求和。

打 LOJ 的 VP 的时候写暴力+卡常拿了 83pts...

其实 YY 出做法是不困难的,考虑维护深度模 K 意义下相同的节点,建 K 颗树即可。

k 较大的时候暴力跳,否则 dfs 序+树状数组统计。

对于修改操作,用并查集将都是 1 的串起来即可,开方 log 次就变成 1 了,和花神游历各国那题是一样的。

然后就没了...

结果巨不好写,BZOJ 也挺卡常的...

 


一个非常弱的准退役OIER