当前位置: 首页 > 工具软件 > Barbecue > 使用案例 >

DTOJ 4771. Barbecue

袁安志
2023-12-01

题意

Lyra 去野外旅游,准备试验刚买的烧烤架,于是她走到了附近的一棵树下想把树的一部分砍下来作为燃料。

树可以看成一棵 n n n 个点编号为 1 ⋯ n 1 \cdots n 1n 的有向无环图, Lyra 要求她砍下来的部分必须是一个连通块,编号也必须连续,她想知道她有多少种不同的砍法。

即给定一棵树,问多少个不同的区间 [ L , R ] [L,R] [L,R] 满足编号为 [ L , R ] [L,R] [L,R] 的点在树上组成一个连通块。

对于 20% 的数据, n ≤ 300 n \le 300 n300

对于 40% 的数据, n ≤ 2000 n \le 2000 n2000

对于额外 20% 的数据,输入构成一条链;

对于 100% 的数据, T ≤ 15 , 1 ≤ u , v ≤ n ≤ 3 × 1 0 5 , ∑ n ≤ 2 × 1 0 6 T \le 15,1 \le u,v \le n \le 3 \times 10^5,\sum n \le 2 \times 10^6 T15,1u,vn3×105,n2×106

题解

一条链可以考虑在链上分治,每次需要计算 [ l , r ] [l,r] [l,r]内跨过 m i d mid mid的合法区间个数,合法区间 [ l , r ] [l,r] [l,r]等价于 m x − m n = r − l mx-mn=r-l mxmn=rl,于是枚举 r r r,用指针维护一下所有 l l l应该贡献在哪里,用数组记一下即可(这比正解难写多了。。。)

对于树上,不知道为什么原本会往点分治想,但联通块的问题效率是无法保证的!!!

于是只能考虑对于编号分治了,但一段编号区间联通怎么转化呢?
注意到树的结构的特殊性,即两个点之间有且仅有一条简单路径,所以这段区间的任意两个点之间的所有点都应出现在区间中。
这样还是不好算,又注意到只需要一一个点为媒介,其它所有点到这个点的路径上的点都出现在区间中即可。
于是以 m i d mid mid为根,区间内所有点到 m i d mid mid的路径上的点都要在区间内,记每个点到 m i d mid mid路径上的点的最大最小值 m n , m x mn,mx mn,mx,即 [ l , r ] [l,r] [l,r] m n mn mn的最小值 = l =l =l m x mx mx的最大值 = r =r =r,于是枚举 r r r,对于合法的 r r r,维护 l l l的合法区间,计算区间内有多少个合法的 l l l即可。

 类似资料:

相关阅读

相关文章

相关问答