환상 향 의 일상

제목 링크
시간 제한:
20000ms
단일 시간:
1000ms
메모리 제한:
256MB
묘사 하 다.
환상 향 에는 모두 n 곳 의 거처 가 있 고 번 호 는 1 에서 n 까지 이다.이 거 처 는 n - 1 개의 변 으로 연결 되 어 나무 모양 의 구 조 를 형성 했다.
거처 마다 작은 요정 이 살 고 있 습 니 다.매일 작은 엘 프 들 은 한 구간 [l, r] 을 골 라 서 거주 번호 가 이 구간 에 있 는 작은 엘 프 와 함께 임 무 를 수행 합 니 다.
특히 이웃 에 있 는 (가장자리 가 연 결 된) 두 요정 은 자발적으로 한 팀 을 구성 하고 a 와 b 가 b 와 인접 하면 a 와 c 도 같은 팀 에 있다.매일 퀘 스 트 를 완성 하면 파티 가 해 체 됩 니 다.다음날 다시 새로운 구간 에 따라 새로운 대 오 를 구성한다.
매일 작은 엘 프 들 이 뽑 는 구간 을 알려 드 리 겠 습 니 다. 매일 구 성 된 파티 수 를 아 십 니까?
입력
첫 번 째 줄 의 두 수 n 과 Q (1 < = n, Q < = 100000) 는 거소 의 수 와 파티 의 일 수 를 나타 낸다.
다음 n - 1 줄 은 줄 마다 두 개의 수 a 와 b 로 거소 a 와 b 사이 에 한 변 이 있 음 을 나타 낸다.
다음 Q 줄, 줄 당 두 개의 수 l 과 r 를 만족 시 켜 1 < = l < = r < = n, 이 날 작은 엘 프 가 선택 한 구간 입 니 다.
출력
Q 줄 을 출력 합 니 다. 줄 마다 정 수 는 이 날 파티 의 수 를 표시 합 니 다.
샘플 입력

3 1
1 2
2 3
1 3

샘플 출력

1

문제 풀이: 그림 은 나무 이기 때문에 이 문 제 는 매우 중요 한 성질 이 있다. 한 점 구간 [L, R] 의 연결 블록 수 는 이 구간 의 포인트 와 같 고 이 구간 의 점 과 점 사이 의 변 수 를 줄인다.
변 (u, v), u < v 에 대해 서 는 하위 구간 [u, v] 으로 봅 니 다.그러면 문 제 는 [L, R] 구간 에 몇 개의 하위 구간 이 포함 되 어 있 는 지 를 구 하 는 것 으로 전환한다.이것 은 고전적 인 문제 다.오프라인 으로 질문 을 처리 하고 R 값 에 따라 작은 것 부터 큰 것 까지 정렬 합 니 다.1 에서 n 까지 쓸 어 올 리 면 한 구간 의 오른쪽 값 v 는 왼쪽 값 u 에 1 을 추가 합 니 다.우리 가 문의 한 오른쪽 값 r 를 만 났 을 때, 이것 은 모든 방문 한 하위 구간 의 오른쪽 값 이 < = R 입 니 다. 왜냐하면 우 리 는 이미 방문 한 하위 구간 의 왼쪽 값 에 1 을 더 했 기 때 문 입 니 다. 이때 구간 [L, R] 의 합 은 바로 이 구간 의 하위 구간 의 수 입 니 다.
코드 는 다음 과 같 습 니 다:

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#define mod 1000000007
#define nn 110000
typedef long long LL;
using namespace std;
struct node
{
    int en,next;
}E[nn*2];
int n,q;
int p[nn],num;
void init()
{
    memset(p,-1,sizeof(p));
    num=0;
}
void add(int st,int en)
{
    E[num].en=en;
    E[num].next=p[st];
    p[st]=num++;
}
struct ask
{
    int id;
    int l,r;
}a[nn];
int ans[nn];
bool cmp(ask x,ask y)
{
    return x.r<y.r;
}
int tree[nn];
inline int lowbit(int x)
{
    return (x&-x);
}
void jia(int id,int x)
{
    for(int i=id;i<=n;i+=lowbit(i))
    {
        tree[i]+=x;
    }
}
int sum(int id)
{
    int re=0;
    while(id)
    {
        re+=tree[id];
        id-=lowbit(id);
    }
    return re;
}
int main()
{
    int i,u,v;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        init();
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        for(i=1;i<=q;i++)
        {
            scanf("%d%d",&a[i].l,&a[i].r);
            a[i].id=i;
        }
        sort(a+1,a+q+1,cmp);
        memset(tree,0,sizeof(tree));
        int ix=1,w;
        for(i=1;i<=n;i++)
        {
            for(int j=p[i];j+1;j=E[j].next)
            {
                w=E[j].en;
                if(w<i)
                {
                    jia(w,1);
                }
            }
            while(i==a[ix].r&&ix<=q)
            {
                ans[a[ix].id]=a[ix].r-a[ix].l+1-(sum(a[ix].r)-sum(a[ix].l-1));
                ix++;
            }
        }
        for(i=1;i<=q;i++)
        {
            printf("%d
",ans[i]);
        }
    }
    return 0;
}