给出N个点的树，编号为1～N，每次的查询为[L, R]，想知道编号在[L, R]内的所有的结点的会被分成多少个连通块。
给出一条性质：连通块数量 = 点数 - 边数。
点数很方便的可以计算，就是"R - L + 1"，那么，如何计算边数呢？
我们知道，每条边有且只有两个结点，由u、v两个点连接形成一条边，所以，如果两者中有一个不存在，那么，这条边也就不存在了，所以，我们给上“+1”，表示有一条边，也就是给u、v中编号小的“+1”用以记录边，这样做有什么好处呢？如果查询的区间包含了u、v那么自然会存在这条边，如果查询的区间不包含
，那么自然这条边也就不存在了。
所以，我们可以离线来完成这个查询操作，按照右端点升序，然后不断的更新，我们就可以很好的维护其这条信息了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define eps 1e-4
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, Q, head[maxN], cnt, ans[maxN] = {0};
struct Eddge
{
int nex, to;
Eddge(int a=-1, int b=0):nex(a), to(b) {}
} edge[maxN << 1];
inline void addEddge(int u, int v)
{
edge[cnt] = Eddge(head[u], v);
head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
struct Question
{
int l, r, id;
Question(int a=0, int b=0, int c=0):l(a), r(b), id(c) {}
inline void In(int ith) { scanf("%d%d", &l, &r); id = ith; }
friend bool operator < (Question e1, Question e2) { return e1.r < e2.r; }
} q[maxN];
int trie[maxN] = {0};
inline void update(int x, int val) { while(x <= N) { trie[x] += val; x += lowbit(x); } }
inline int query(int x) { int sum = 0; while(x) { sum += trie[x]; x -= lowbit(x); } return sum; }
inline void init()
{
cnt = 0;
for(int i=1; i<=N; i++) { head[i] = -1; trie[i] = 0; }
}
int main()
{
scanf("%d%d", &N, &Q);
init();
for(int i=1, u, v; i<N; i++)
{
scanf("%d%d", &u, &v);
_add(u, v);
}
for(int i=1; i<=Q; i++) q[i].In(i);
sort(q + 1, q + Q + 1);
for(int qi=1, u = 1; qi<=Q; qi++)
{
while(u <= q[qi].r)
{
for(int i=head[u], v; ~i; i=edge[i].nex)
{
v = edge[i].to;
if(v < u)
{
update(v, 1);
}
}
u++;
}
ans[q[qi].id] = q[qi].r - q[qi].l + 1 - (query(q[qi].r) - query(q[qi].l - 1));
}
for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
return 0;
}