记录编号	589304	评测结果	AAAAAAAAAA
题目名称	飘雪圣域	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	3.079 s
提交时间	2024-07-04 17:29:52	内存使用	5.54 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n,q;
struct node
{
	int x,y;
}bian[N];int c[N];
int lowbit(int x){return x&(-x);}
void add(int x,int val){
	for(;x<=n;x+=lowbit(x))c[x]+=val;
}

struct Ask{
	int l,r,i;
}ask[N];
int get(int x){
	int sum=0;
	for(;x;x-=lowbit(x))sum+=c[x];
	return sum;
}
int ans[N];
bool cmp(node a,node b){return a.y<b.y;}
bool cm(Ask a,Ask b){return a.r<b.r;}
int main(){
    freopen("icekingdom.in","r",stdin);
    freopen("icekingdom.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<n;++i){
		cin>>bian[i].x>>bian[i].y;
		if(bian[i].x>bian[i].y)swap(bian[i].x,bian[i].y);
	}
	sort(bian+1,bian+n,cmp);
	for(int i=1;i<=q;++i){
	   cin>>ask[i].l>>ask[i].r;
		ask[i].i=i;
	}
	sort(ask+1,ask+1+q,cm);
	for(int i=1,j=1;i<=q;++i){
	   while(bian[j].y<=ask[i].r&&j<n){
		    add(bian[j].x,1);++j;
		}
		ans[ask[i].i]=ask[i].r-ask[i].l+1-get(ask[i].r)+get(ask[i].l-1);
	}
	for(int i=1;i<=q;++i)cout<<ans[i]<<endl;
	return 0;
}