虚树是一种统计树上信息的技术
如果树的点数很少,可以直接树上dp
可以发现
我们可以每次都把提供
查看原题
点击跳转
操作是否有效
接下来很容易可以想到树剖+线段树优化建图
很可惜,出题人卡了这种大常数做法
考虑直接在树上倍增优化建图
和倍增lca差不多,一直向上连边
而每个点又拆为入点和出点
每次构建传送门时新建一个点,
连边时只需要
所在的块出点连接新建点,新建点连接
所在的块入点
详细见代码
记录每个点
前一个与它一样的位置
,
那么区间
内不同的个数也就是
中
的个数
主席树统计即可
考虑每个点对答案的贡献,分类讨论
那么满足的
或
总贡献为
(
为了避免
被重复计算)
拆下式子:
可以发现这种情况可以直接前缀和维护
,满足
那么满足的
总贡献为
拆下式子
可以发现这种情况可以用主席树维护
观察数据形成方式:
p
个点形成一条主链,其他点随机向主链连边\texttt{lca}
距离他们期望为\mathcal O(\log n)
[1,n]
中随机,每种颜色数目期望为1
令
为
的祖先中颜色与
相同的深度最大的点
设
与
中
离
更近
首先求出
到
链上的颜色总数,
然后再暴力枚举
到
链上的颜色更新答案
设
与
中
离
更近
分类讨论:
x\in [1,\texttt{lca}],y\in [1,B]
,与链上的情况相同用
的答案减去
的答案
拆下式子:
先求出
的贡献
拆下式子:
然后用
更新
,设
为
中第一个与它颜色相同的点
贡献:
题意: 给一颗树,每条边权值可以修改为
,使得修改后这条边可以在最小生成树上,问
最大可以是多少?
首先求出最小生成树(以下的树指最小生成树)
修改一条边时,若不是最小生成树上的边,则为树上该边两端节点之间的最大值
若是树上的边,那么就是该边子树中找出一些非树边(使它们最大值尽可能小)连接除子树部分的点,答案为该边权值
看上去不是很好处理
我们将非树边按权值从小到大排序,从下往上合并,用并查集维护即可
每次遇到非树边
时,就更新并合并
,从下往上跳时,并查集可以跳过已经打过标记的边
详见代码
线性基搬到了树上
线性基是支持合并的
这题就是倍增暴力合并线性基
虽然
的复杂度已经可以通过了,但是还有更优的方法
在倍增找出询问两点的lca,然后以rmq的方式合并+查询线性基,可以将复杂度降到
交互题
我们从叶子节点开始搜索,把所有叶子节点添加到队列中
每次从队列中弹出两个叶子节点,
如果lca
为其中一个,那么这个lca
就是树根
否则删除这两个节点,可能会形成新的叶子节点,加入队列
因为最坏情况下每次都会删掉两个节点,那么重复
次后,也就只剩下根节点了
可以发现有三种路径:
只需要判断这三条路径是否满足就可以了
可以发现只要
而且和
同奇偶就是符合的
(比如
可以一直循环,变成
,每次长度
)