记录编号	589248	评测结果	AAAAAAAAAA
题目名称	飘雪圣域	最终得分	100
用户昵称	darkMoon	是否通过	通过
代码语言	C++	运行时间	0.838 s
提交时间	2024-07-04 14:37:57	内存使用	13.50 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 2e5 + 5;
int n = mread(), q = mread(), ans[N], s2[N];
vector<int> v[N];
struct node{
    int l, r, id;
}s[N];
pair<int, int> p[N];
void add(int x, int k){
    while(x <= n){
        s2[x] += k;
        x += x & -x;
    }
    return;
}
int query(int x){
    int ans = 0;
    while(x){
        ans += s2[x];
        x -= x & -x;
    }
    return ans;
}
signed main(){
    for(int i = 1, x, y; i < n; i ++){
        p[i].fi = mread(), p[i].se = mread();
        if(p[i].fi > p[i].se)
        swap(p[i].fi, p[i].se);
    }
    sort(p + 1, p + n, [](pair<int, int> a, pair<int, int> b){
        return a.se < b.se;
    });
    for(int i = 1; i <= q; i ++){
        s[i].l = mread(), s[i].r = mread();
        s[i].id = i;
    }
    sort(s + 1, s + 1 + q, [](node a, node b){
        return a.r < b.r;
    });
    int idx = 1, now = 1;
    for(int i = 1; i <= n; i ++){
        while(now < n && p[now].se == i){
            add(p[now].fi, 1);
            now ++;
        }
        while(idx <= q && s[idx].r == i){
            ans[s[idx].id] = s[idx].r - s[idx].l + 1 - (now - 1 - query(s[idx].l - 1));
            idx ++;
        }
    }
    for(int i = 1; i <= q; i ++)
    printf("%lld\n", ans[i]);
    return 0;
}