Yet Another Tree Query Problem

Time Limit: 3 Seconds Memory Limit: 65536 KB

Given a tree with vertices, which are numbered by integers from 1 to n, there are queries.
Each query can be described with two integers and . A vertex is good, if and only if l≤v≤rl\leq v \leq r; An edge is good, if and only if both and are good. Please print the number of connected components consist of all the good vertices and the good edges.

Input

There are multiple test cases. The first line of the input is an integer T (about 5), indicating the number of test cases. For each test case:
The first line contains two integers n and q (1≤n,q≤2×1051\leq n,q \leq 2\times 10^5), indicating the number of vertices and the number of queries.
The following n−1n-1 lines each contains two integers u and v(1≤u,v≤n1\leq u,v\leq n), indicating an edge connecting vertex and in the tree.
The following q lines each contains two integers l and r (1≤l≤r≤n1\leq l\leq r\leq n), indicating a query.
It’s guaranteed that the given graph is a tree.

Output

For each query output one line containing one integer, indicating the answer.

Sample Input

2
4 6
1 4
4 3
3 2
1 2
2 3
3 4
1 3
2 4
1 4
3 2
1 3
2 3
1 2
2 3

Sample Output

2
1
1
2
1
1
2
1

Hint

For the six queries in case 1, the connected components are listed as follows:
[1], [2]
[2, 3]
[3, 4]
[1], [2, 3]
[2, 3, 4]
[1, 2, 3, 4]
For the two queries in case 2, the connected components are as follows:
[1], [2]
[2, 3]

题意：

给出一个有n个结点的树，结点为1−n1-n.输入n-1行表示所有边u，v。 每个询问都会给出l，r。
good point为数字在[l,r][l,r]的点。good edge为两个good point连起来的边。good component为几个good point 或 edge 连起来的部分。对于每次询问l，r，求出有多少个good component。

解法

good component的数量其实就是good point-good edge .
good point=r-l+1.
问题就在good edge上，good edge 的条件是两个端点都在[l,r][l,r]，普通做法就是O(N2)O(N^2).
如何求出这个数量呢？

在图中，以u,v为坐标轴，那么每个边都是图上的一个点，每次查询也是一个关键点，所需要的答案就是黄色矩形中的点的数量

我们知道一维线段树是一个线段每次对半分开，作为其两个儿子，那么二维线段树就是矩形的中间分开分成四份作为其四个儿子。具体操作和一维线段树一样。
以此类推三维线段树是立方体从中心分成8份，四维线段树每次分成16份。。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<set>
#include<math.h>
#include<stack>
using namespace std;
typedef long long LL;
struct node
{
	int num;
	int son[4];
}tree[2000000];
/*
0|1
-+-
2|3
*/
int total;
int answer;
void update(int temp, int left, int right, int up, int down, int x, int y)
{
	if (left == right && up == down)
	{
		tree[temp].num = 1;
		return;
	}
	int mid1 = left + right >> 1;
	int mid2 = up + down >> 1;
	if (x <= mid1)
	{
		if (y <= mid2)
		{
			if (tree[temp].son[0] == 0)
				tree[temp].son[0] = ++total;
			update(tree[temp].son[0], left, mid1, up, mid2, x, y);
		}
		else
		{
			if (tree[temp].son[2] == 0)
				tree[temp].son[2] = ++total;
			update(tree[temp].son[2], left, mid1, mid2 + 1, down, x, y);
		}
	}
	else
	{
		if (y <= mid2)
		{
			if (tree[temp].son[1] == 0)
				tree[temp].son[1] = ++total;
			update(tree[temp].son[1], mid1 + 1, right, up, mid2, x, y);
		}
		else
		{
			if (tree[temp].son[3] == 0)
				tree[temp].son[3] = ++total;
			update(tree[temp].son[3], mid1 + 1, right, mid2 + 1, down, x, y);
		}
	}
	tree[temp].num = 0;
	for (int i = 0; i < 4; i++)
	{
		tree[temp].num += tree[tree[temp].son[i]].num;
	}
}
void query(int temp, int left, int right, int up, int down, int x, int y)
{
	if (left >= x && down <= y)
	{
		answer += tree[temp].num;
		return;
	}
	int mid1 = left + right >> 1;
	int mid2 = up + down >> 1;
	if (x <= mid1)
	{
		if (y > mid2)
		{
			if (tree[temp].son[2] != 0)
				query(tree[temp].son[2], left, mid1, mid2 + 1, down, x, y);
		}
		if (tree[temp].son[0] != 0)
			query(tree[temp].son[0], left, mid1, up, mid2, x, y);
	}
	if (y > mid2)
	{
		if (tree[temp].son[3] != 0)
			query(tree[temp].son[3], mid1 + 1, right, mid2 + 1, down, x, y);
	}
	if (tree[temp].son[1] != 0)
		query(tree[temp].son[1], mid1 + 1, right, up, mid2, x, y);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		total = 1;
		memset(tree, 0, sizeof(tree));
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i < n; i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			if (a > b)
				swap(a, b);
			update(1, 1, n, 1, n, a, b);
		}
		for (int i = 0; i < m; i++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			answer = 0;
			query(1, 1, n, 1, n, a, b);
			printf("%d\n", b - a - answer + 1);
		}
	}
}

总结:


给出很多区间如图，如何快速求出[l,r][l,r]内的区间（左端点大于ll且右端点小于rr）。对于图中的情况答案应该为2。
这类问题就可以用二维线段树将每个区间都转变为二维平面上的一个点P(u,v)P(u,v)，
所求的答案就是

sum({P(u,v)∣l≤u≤v≤r})sum(\{ P(u,v)|l\leq u\leq v\leq r\})

用线段树维护区间和即可