#1145 : 幻想乡的日常
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
幻想乡一共有n处居所，编号从1到n。这些居所被n-1条边连起来，形成了一个树形的结构。
每处居所都居住着一个小精灵。每天小精灵们都会选出一个区间[l,r]，居所编号在这个区间内的小精灵一起来完成一项任务。
特别的，居所相邻的(有边相连的)两个小精灵会自发的组成一队，并且如果a和b相邻b和c相邻，那么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
/**
题意：在一个去见内，求有多少子区间；
做法：树状数组 + 离散化
**/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <queue>
#define maxn 110000
using namespace std;
int sum[maxn];
int mmap[maxn];
int n,m;
int num;
int head[maxn];
struct Line
{
int l;
int r;
int id;
} line[maxn];
int cmp(Line a,Line b)
{
return a.r < b.r;
}
struct Node
{
int val;
int next;
} node[maxn*];
void init()
{
num = ;
memset(head,-,sizeof(head));
}
void addedge(int u,int v)
{
node[num].val = v;
node[num].next = head[u];
head[u] = num++;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int u,int v)
{
for(int i=u; i<=n; i += lowbit(i))
{
sum[i] += v;
}
}
int getsum(int u)
{
int sumweight = ;
while(u)
{
sumweight += sum[u];
u -= lowbit(u);
}
return sumweight;
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("in.txt","r",stdin);
//#endif // ONLINE_JUDGE
while(~scanf("%d %d",&n,&m))
{
int u,v;
init();
for(int i=; i<n; i++)
{
scanf("%d %d",&u,&v);
addedge(u,v);
addedge(v,u);
}
for(int i=; i<=m; i++)
{
scanf("%d %d",&line[i].l,&line[i].r);
line[i].id = i;
}
int ix =,ans = ;
memset(mmap,,sizeof(mmap));
sort(line+,line+m+,cmp);
memset(sum,,sizeof(sum));
for(int i=; i<=n; i++)
{
for(int j=head[i]; j+; j=node[j].next)
{
int w = node[j].val;
if(w < i)
{
add(w,);
}
}
while(i == line[ix].r && ix <= m)
{
mmap[line[ix].id] = line[ix].r - line[ix].l + - (getsum(line[ix].r) - getsum(line[ix].l -));
ix ++;
}
}
for(int i=; i<=m; i++)
{
printf("%d\n",mmap[i]);
}
}
return ;
}