F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5457. -- 城市

5457: 城市

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 53  Solved: 29
[Submit][Status][Discuss]

Description

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

Input

共有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。

Output

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

Sample Input

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

Sample Output

2 13
1 10
5 6
1 10
1 10
5 6
1 10
4 6

HINT

Source

[Submit][Status][Discuss]

HOME Back