题解:

弹球题目地址:https://www.nowcoder.com/acm/contest/113/E

后面这题 应该是天天爱跑步的加强版本

原理都是查询子树中dep[x]+f[x]的值的个数

由树变成了基环树

天天爱跑步我以前写过splay启发式合并和树剖

因为是离线,现在发现直接差分应该更加弱智

所以在一个点加这个数一个点减这个就可以了

然后直接dfs一遍就可以了

拿个数组维护就好了

然后弹球这题

就是维护dep[x]+time[x]的值的个数

然后由于他这个是要动态维护的

所以我们可以对每个数值维护一颗线段树

然后每次在对应线段树上进行单点插入

然后是查询子树,这是一个区间,所以可以直接查询

我发现claris好强啊每次想到的都是最优的

我自己想的是用树剖来nlog^2来维护。。

然后问题就变成了怎么处理环

我们要让树中节点进入环中

所以我们要把环中的节点建的相邻的

这我们可以开个数组记录一下进入环中的时间

另外再给环中节点编个号,然后%环长大小相同

然后再开一个数组记录环中的信息

因为要%环长了 所以直接vector记录就可以了

04-26 00:56