#P15234. [2026队内训练]scimoon 的树学题

    ID: 14450 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200莫队LCA数据结构图论DFS排序数学

[2026队内训练]scimoon 的树学题

Description

这是一棵有 nn 个柠檬的柠檬树,由 n−1n-1 条枝条连接而成。

秋天了,柠檬都成熟了, scimoon\color{black}{\texttt{s}}\color{red}{cimoon} 准备选一些柠檬送给他的朋友们。

对于每一个朋友,scimoon\color{black}{\texttt{s}}\color{red}{cimoon} 会选择第 l−rl-r 个柠檬送给她。具体的采摘方法是:选取尽可能少的树枝,使得区间内的柠檬两两连通。

scimoon\color{black}{\texttt{s}}\color{red}{cimoon} 急于送柠檬,但他的朋友太多啦,他实在是忙的上气不接下气。所以他想让您来帮忙。

Input

第一行,输入 n,qn,q ,表示柠檬数和朋友数 。

接下来 n−1n-1 行,每行输入 uu 和 vv ,表示一条枝条连接了 uu 和 vv 。

接下来 qq 行,每行输入 ll 和 rr ,表示 scimoon\color{black}{\texttt{s}}\color{red}{cimoon} 送给这位朋友第 l−rl-r 个柠檬。

Output

输出共 qq 行,每行输出选取尽可能少的树枝数。

Samples

  • Input #1

    5 3
    1 2
    2 3
    3 4
    4 5
    1 3
    1 5
    4 5
    
  • Output #1

    2
    4
    1
    
  • Explanation #1

对于第一组询问,至少需要第11条和第22条树枝,这样两条边1−21-2和2−32-3能将11和33苹果连接起来。

对于第二组询问,这44条树枝都必须取,此时四条边能将11到55这5个苹果连接起来。

  • Input #2

    5 5
    2 1
    3 2
    2 4
    5 4
    1 3
    4 5
    1 3
    2 3
    2 5
    
  • Output #2

    2
    1
    2
    1
    3
    

Constriants

本题采用 subtasksubtask 。

subtask1(10 pts):1≤n≤5,1≤q≤5subtask1(10 \ pts): 1\le n\le 5, 1\le q\le 5;

subtask2(10 pts):1≤n≤10,1≤q≤50subtask2(10\ pts): 1\le n\le 10, 1\le q\le 50;

subtask3(20 pts):1≤n≤1000,1≤q≤1000subtask3(20\ pts): 1\le n\le 1000, 1\le q\le 1000;

$subtask4(10\ pts): 1\le n\le 10000, 1\le q\le 10000$,保证数据随机;

$subtask5(10\ pts): 1\le n\le 10000, 1\le q\le 10000$,不保证数据随机;

$subtask6(40\ pts): 1\le n\le 50000, 1\le q\le 50000$。