题目描述
小X是远近闻名的学佛，平日里最喜欢做的事就是蒸发学水。
小X所在的城市X城是一个含有N个节点的无向图，同时，由于X国是一个发展中国家，为了节约城市建设的经费，X国首相在建造X城时只建造N-1条边，使得城市的各个地点能够相互到达。
小X计划蒸发Q天的学水，每一天会有一名学水从A地走到B地，并在沿途各个地点留下一个水塘。此后，小X会从C地走到B地，并用佛光蒸发沿途的水塘。由于X城是一个学佛横行的城市，学水留下的水塘即使没有被小X蒸发，也会在第二天之前被其他学佛蒸发殆尽。
现在，小X想要知道，他每一天能够蒸发多少水塘呢？
输入格式
第一行三个整数N, Q, num，分别表示X城地点的个数，小X蒸发学水的天数，以及测试点编号。注意，测试点编号是为了让选手们更方便的获得部分分，你可能不需要用到这则信息，在下发的样例中，测试点编号的含义是该样例满足某一测试点限制。
接下来N-1行，每行两个整数X, Y，表示X地与Y地之间有一条边。
接下来Q行，每行三个整数A, B, C，表示一天中，有一名学水从A地走到B地，而小X会从C地走到B地。
输出格式
输出Q行，每行一个整数，表示小X能够蒸发的水塘数。
样例
输入
3 3 1
1 2
2 3
1 2 3
1 1 3
3 1 3输出
1
1
3【数据范围】
| 测试点编号 | N | Q | 特殊性质 1 | 特殊性质 2 |
|---|---|---|---|---|
| 1 | ≤10 | ≤10 | NO | NO |
| 2 | ≤10 | ≤10 | NO | NO |
| 3 | ≤10 | ≤10 | NO | NO |
| 4 | ≤10 | ≤10 | NO | NO |
| 5 | ≤1000 | ≤1000 | NO | NO |
| 6 | ≤1000 | ≤1000 | NO | NO |
| 7 | ≤1000 | ≤1000 | NO | NO |
| 8 | ≤$10^5$ | ≤30 | YES | YES |
| 9 | ≤$10^5$ | ≤30 | YES | YES |
| 10 | ≤$10^5$ | ≤30 | YES | YES |
| 11 | ≤$10^5$ | ≤$10^5$ | YES | YES |
| 12 | ≤$10^5$ | ≤$10^5$ | YES | NO |
| 13 | ≤$10^5$ | ≤$10^5$ | YES | NO |
| 14 | ≤$10^5$ | ≤$10^5$ | YES | YES |
| 15 | ≤$10^5$ | ≤$10^5$ | NO | NO |
| 16 | ≤$10^5$ | ≤$10^5$ | NO | NO |
| 17 | ≤2 * $10^5$ | ≤2 * $10^5$ | YES | YES |
| 18 | ≤2 * $10^5$ | ≤2 * $10^5$ | YES | NO |
| 19 | ≤2 * $10^5$ | ≤2 * $10^5$ | YES | YES |
| 20 | ≤2 * $10^5$ | ≤2 * $10^5$ | NO | NO |
特殊性质 1：第 ( i ) 条边连接第 ( i + 1 ) 个地点。
特殊性质 2：( A = C )。
鲁ICP备2025150228号