记录编号	589266	评测结果	AAAAAAAAAA
题目名称	飘雪圣域	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	3.437 s
提交时间	2024-07-04 15:41:51	内存使用	11.68 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200005
ll s[MAXN];
ll n,m,cnt1=1,cnt2=1;
struct node{
    ll l,r,ans,num;
}line[MAXN],qs[MAXN];
bool cmp(node a,node b){
    return a.l<b.l;
}
bool res(node a,node b){
    return a.num<b.num;
}
ll lowbit(ll idx){
    return idx&(-idx);
}
void ad_(ll idx,ll adz){
    while(idx<=n){
        s[idx]+=adz;
        idx+=lowbit(idx);
    }
}
ll re_(ll idx){
    ll ans=0;
    while(idx){
        ans+=s[idx];
        idx-=lowbit(idx);
    }
    return ans;
}
int main(){
    freopen("icekingdom.in","r",stdin);
    freopen("icekingdom.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        ll l=min(x,y),r=max(x,y);
        line[i].l=l,line[i].r=r;
        ad_(line[i].r,1);
    }
    for(int i=1;i<=m;i++){
        
        cin>>qs[i].l>>qs[i].r;
        qs[i].num=i; 
    }
    sort(line+1,line+n,cmp);
    sort(qs+1,qs+1+m,cmp);
    for(int i=1;i<=n;i++){
        while(cnt2<=m){
            if(qs[cnt2].l==i){
                qs[cnt2].ans=1-re_(qs[cnt2].r)+re_(qs[cnt2].l-1)+qs[cnt2].r-qs[cnt2].l;
                cnt2++;
            }else break;
        }
        while(cnt1<n){
            if(line[cnt1].l==i){
                ad_(line[cnt1].r,0-1);
                cnt1++;
            }else break;
        }
    } 
    sort(qs+1,qs+1+m,res);
    for(int i=1;i<=m;i++){
        cout<<qs[i].ans<<endl;
    }
    return 0;
}