编程介的小学生 2019-02-22 01:12 采纳率: 20.5%
浏览 246

动态节点的分配如何优化这个的算法, 采用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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 spring后端vue前端
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题