三元组队列的查询的算法,采用C语言编程的技术的实现的方式

Problem Description
Three countries, Red, Yellow, and Blue are in war. The map of battlefield is a tree, which means that there are N nodes and (N – 1) edges that connect all the nodes. Each country has a base station located in one node. All three countries will not place their station in the same node. And each country will start from its base station to occupy other nodes. For each node, country A will occupy it iff other two country's base stations have larger distances to that node compared to country A. Note that each edge is of the same length.

Given three country's base station, you task is to calculate the number of nodes each country occupies (the base station is counted).

Input
The input starts with a single integer T (1 ≤ T ≤ 10), the number of test cases.

Each test cases starts with a single integer N (3 ≤ N ≤ 10 ^ 5), which means there are N nodes in the tree.

Then N - 1 lines follow, each containing two integers u and v (1 ≤ u, v ≤ N, u ≠ v), which means that there is an edge between node u and node v.

Then a single integer M (1 ≤ M ≤ 10 ^ 5) follows, indicating the number of queries.

Each the next M lines contains a query of three integers a, b, c (1 ≤ a, b, c ≤ N, a, b, c are distinct), which indicates the base stations of the three countries respectively.

Output
For each query, you should output three integers in a single line, separated by white spaces, indicating the number of nodes that each country occupies. Note that the order is the same as the country's base station input.

Sample Input
1
9
1 2
1 3
1 4
2 5
2 6
2 7
6 8
6 9
2
1 2 8
2 1 4

Sample Output
3 3 1
6 2 1

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问