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

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct edge{
    int x,y;
}e[200010];
struct question{
    int l,r,bh;
}q[200010];
int n,m,tree[200010],ans[200010];
int ask(int x)
{
    int ans=0;
    for(;x;x-=x&-x)
    {
        ans+=tree[x];
    }
    return ans;
}
void add(int x,int y)
{
    for(;x<=n;x+=x&-x)
    {
        tree[x]+=y;
    }
}
bool cmp1(edge a,edge b)
{
    return a.y<b.y;
}
bool cmp2(question a,question b)
{
    return a.r<b.r;
}
int main()
{
    freopen("icekingdom.in","r",stdin);
    freopen("icekingdom.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&e[i].x,&e[i].y);
        if(e[i].x>e[i].y) swap(e[i].x,e[i].y);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].bh=i;
    }
    sort(e+1,e+n,cmp1);
    sort(q+1,q+m+1,cmp2);
    int now=1;
    for(int i=1;i<=m;i++)
    {
        while(q[i].r>=e[now].y&&now<n)
        {
            add(e[now].x,1);
            now++;
        }
        int s=ask(q[i].r)-ask(q[i].l-1);
        ans[q[i].bh]=q[i].r-q[i].l+1-s;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}