一棵 n 个节点的有标号无根树, 求这样的路径 u-v (u≠v) 的数目: 路径上不存在点对 (a,b) (a≠b) 满足 gcd(a,b) = a. u-v, v-u 算作同一条.
- 10%: n ≤ 500
- 30%: n ≤ 3000
- 50%: n ≤ 30000
- 另 30%: 树是一条链
- 100%: n ≤ 10^5 gcd(a,b) = a <=> b 是 a 的倍数
冷静了一下, 发现暴力还是好写的......注意 a,b 这些都是 [1,n] 内的整数. 倍数关系只有
对于一条链的情形. 设 left[x] = x 的左边最靠右的 y 的位置, 使得 y 是 x 的约数或倍数 (称这样的 (x,y) 为一个限制). 固定右端点 r, 待求的便是最靠左的 l, 使得 pos[l] > max { left[x] | l ≤ x ≤ r }. r 右移, 会使 max { } 这部分非严格递增, 迫使 l 不能左移.
或者这样想: 一个区间内没有限制意味着它的子区间内没有限制. 如果 r 右移之后 l 可以左移, 就与之前 l 的最优性相悖.
总而言之, 有单调性, 可以用 two-pointers 扫一扫.
想了一下问题的反面, 即包含至少一个限制的路径的条数. 好像它们的特征比较容易刻画......但是容斥什么的好麻烦还是算了吧......
就这样, 正解又偷偷溜走啦!!
它们的特征是什么呢? 设 (x,y) 是一个限制. dfn[x] < dfn[y]. 路径 s-t 包含它. dfn[s] < dfn[t].
- 如果两者没有祖先-后代的关系, 那么 s-t 必然满足 dfn[s]∈[st[x],ed[x]), dfn[t]∈[st[y],ed[y]).
- 如果 x 是 y 的祖先, 设 y 的祖先 z 是 x 的儿子, 那么 s-t 满足 dfn[s]∈[1,st[z]), dfn[t]∈[st[y],ed[y]), 或者 dfn[s]∈[st[y],ed[y]), dfn[t]∈[ed[z], n].
这些同时也是充分条件.
把 s-t 看成平面上的一个点 (s,t), 这些式子表示的是矩形. 求矩形的面积并.
容斥不一定得手动+1-1啊......遇到容斥就跑, 真是胆小鬼 ╮（﹀＿﹀）╭
不过我好像不能正确而快速地敲出线段树+扫描线求矩形面积并的代码. 区间赋值+历史版本和? 记得没这么麻烦啊......学习了一下......
我写线段树习惯于把标记 push down. 在这个应用中, 不向下压标记反而更容易. 记录每个区间被覆盖多少次, 维护这段区间被覆盖的长度 (不考虑覆盖这整个区间的标记).