Description
给定一棵树 n n n，点带权，求有多少个非空区间 [ l , r ] [l,r] [l,r] 使得存在一种选定方案，使得这些点覆盖了 [ l , r ] [l,r] [l,r] 中的所有整数恰好一次且这些点形成了一个包含根的连通块。
原数据范围:
1
≤
n
≤
1
0
4
,
1
≤
v
i
≤
100
1 \le n \le 10^4,1 \le v_i \le 100
1≤n≤104,1≤vi≤100
加强版数据范围:
1
≤
n
≤
1
0
5
,
1
≤
v
i
≤
1
0
4
1 \le n \le 10^5,1 \le v_i \le 10^4
1≤n≤105,1≤vi≤104
Solution
算法一
考虑 dp \text{dp} dp。
令 f u , l , r f_{u,l,r} fu,l,r 表示，能否在以 u u u 为根的子树中，选出一棵包含 u u u 的连通块且覆盖了 [ l , r ] [l,r] [l,r] 中的全部整数恰好一次。若可以则 f u , l , r = 1 f_{u,l,r}=1 fu,l,r=1，否则 f u , l , r = 0 f_{u,l,r}=0 fu,l,r=0。
然而即使使用 bitset 优化 f f f，其空间依然是无法接受的，所以我们考虑对状态设计进行修改。
注意到， u u u 一定要选（ u u u 作为不需考虑的边界），所以从 u u u 的各个子树中选出来的区间一定不能包含 a u a_u au，并且最终整棵以 u u u 为根的子树中选出来的区间一定要包含 a u a_u au。因此，我们可以将状态一分为二: 令 f u , l , 0 f_{u,l,0} fu,l,0 表示，能否覆盖到 [ l , a u − 1 ] [l,a_u-1] [l,au−1] 中的所有数；令 f u , r , 1 f_{u,r,1} fu,r,1 表示，能否覆盖到 [ a u + 1 , r ] [a_u+1,r] [au+1,r] 中的所有数。那么，真实的 f u , l , r f_{u,l,r} fu,l,r 就是 f u , l , 0 f_{u,l,0} fu,l,0 和 f u , r , 1 f_{u,r,1} fu,r,1 作按位与的结果。这也是本题最精髓的一步，我在考场上并没有想到这一步降维操作，现在是真的学到了。
下面以计算 f u , l , 0 f_{u,l,0} fu,l,0 为例。枚举一个满足 a v < a u a_v<a_u av<au 的点 v v v，若 v v v 往右最远能够扩展到的 x x x（形式化地说， x x x 为最大的满足 f v , x , 1 = 1 f_{v,x,1}=1 fv,x,1=1 的 x x x）满足 u u u 往左最远能够扩展到的位置不超过 x + 1 x+1 x+1， 那么可以将 u u u 与 v v v 的状态合并到一起。具体来说，对于每个 f v , l , 0 = 1 f_{v,l,0}=1 fv,l,0=1，其都可以让 f u , l , 0 = 1 f_{u,l,0}=1 fu,l,0=1，于是我们枚举一个 l l l 并让 f u , l , 0 f_{u,l,0} fu,l,0 对 f v , l , 0 f_{v,l,0} fv,l,0 做按位或。
计算 f u , r , 1 f_{u,r,1} fu,r,1 的方法与其基本相同。
于是，我们愉快地得到了一个 O ( n V ) O(nV) O(nV) 的做法，其中 V V V 是所有 v i v_i vi 的最大值。可以通过原题。
算法二
考虑使用 bitset 优化这个 dp \text{dp} dp。
该如何用二进制快速维护呢？下为方便叙述，仅考虑 f u , l , 0 f_{u,l,0} fu,l,0 的计算； f u , r , 1 f_{u,r,1} fu,r,1 同理。
不难发现，我们所要维护的就是：
- 判断是否同时存在一个 x x x 使得 f v , x , 1 = f u , x + 1 , 0 = 1 f_{v,x,1}=f_{u,x+1,0}=1 fv,x,1=fu,x+1,0=1
- ∀ l \forall l ∀l 将 f u , l , 0 f_{u,l,0} fu,l,0 对 f v , l , 0 f_{v,l,0} fv,l,0 做按位或。
对于前者，将 f u , 0 f_{u,0} fu,0 对应的二进制数左移 1 1 1 位然后将其对 f v , 1 f_{v,1} fv,1 做按位与并判断其是否非 0 0 0 即可。对于后者，直接将 f u , 0 f_{u,0} fu,0 对 f v , 0 f_{v,0} fv,0 做按位或即可。
时间复杂度 O ( n V w ) O(\frac {nV} {w}) O(wnV)，OJ 的位长为 64 64 64，算出来大概是 1.6 × 1 0 7 1.6 \times 10^7 1.6×107 左右，可以通过。
Summary
本题重点在于，通过所有儿子 v v v 都不能覆盖到 a u a_u au 并且最终状态一定要覆盖到 a u a_u au 的性质，将原状态 f u , l , r f_{u,l,r} fu,l,r 一分为二，大大降低了空间复杂度，方便了进一步的 bitset 优化。
妙题！