BZPRO

#5457. 城市

内存限制：512 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述

有n座城市，m个民族。这些城市之间由n-1条道路连接形成了以城市1为根的有根树。每个城市都是某一民族的聚居
地，Master知道第i个城市的民族是A_i，人数是B_i。为了维护稳定，Master需要知道某个区域内人数最多的民族
。他向你提出n个询问，其中第i个询问是：求以i为根的子树内，人数最多的民族有是哪个，这个民族有多少人。
如果子树内人数最多的民族有多个，输出其中编号最小的民族。

输入格式

共有2*n行。
第一行有两个整数n, m。
接下来n-1行，每行有两个整数u, v，表示一条连接u和v的道路。
接下来n行，第i行有两个整数A_i, B_i。
n<=400000，m<=n，1<=A_i<=m，0<=B_i<=1000。

输出格式

共有n行。
第i行两个整数x, y，分别表示以i为根的子树中人数最多的民族和它的人数。

样例

样例输入


			
8 6

1 2

1 3

2 4

4 5

3 6

5 7

1 8

2 8

2 5

1 1

3 1

6 7

5 6

1 10

4 6

样例输出


			
2 13

1 10

5 6

1 10

1 10

5 6

1 10

4 6

数据范围与提示

BZPRO Powered by Remmina.
Github Repository