\(对查询的边x,分为两种情况 \)
\(第一种,x为最大边,只需要找离x最近且比x小的两条边判断a+b>x就够了,此处可用multiset \)
\(第二种,x不是最大边,那么需要找到一个b,使得b \geq x,b-a<x \)[……]
\(对查询的边x,分为两种情况 \)
\(第一种,x为最大边,只需要找离x最近且比x小的两条边判断a+b>x就够了,此处可用multiset \)
\(第二种,x不是最大边,那么需要找到一个b,使得b \geq x,b-a<x \)[……]
\(很明显,记叶子节点数为s,则k=\left \lceil \frac{s}{2} \right \rceil \)
\(那么如何匹配呢?首先要选取一个非叶子节点作为根,然后对其进行dfs得到dfs序\)
$latex 按照dfs序大小排序得到叶子节点u[……]
\(对每个s_i的前缀s_{i, 1…j}进行与所有后缀比较,相同的次数记为res_{i,j},此处可以用哈希进行比较 \)
$latex 因为要取最大前缀,所以要用kmp求出next数组后res_{i,next[j]} -= res_{i, j},注意一下下标的偏[……]
\(令c_i=min_{1\leq i < j, t_j=t_i}\{j-i\} \)
\(B数组其实就是c_1 c_2 c_3 … c_n的后缀数组 \)
$latex 要注意若没有t_j=t_i,则c_i = n,同时c_{n+1}[……]