BJOI2015 骑士的旅行

时间限制:20s      空间限制:512MB

题目描述

在一片古老的土地上,有一个繁荣的文明。
这片大地几乎被森林覆盖,有N座城坐落其中。巧合的是,这N座城由恰好N-1条双
向道路连接起来,使得任意两座城都是连通的。也就是说,这些城形成了树的结构,任意两
座城之间有且仅有一条简单路径。
在这个文明中,骑士是尤其受到尊崇的职业。任何一名骑士,都是其家族乃至家乡的荣
耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后,Henry
终于满18岁了。他决定离开家乡,向那些成名已久的骑士们发起挑战!
根据Henry的调查,大陆上一共有M名受封骑士,不妨编号为1到M。
第i个骑士居住在城Pi,武力值为Fi。
Henry计划进行若干次旅行,每次从某座城出发沿着唯一的简单路径前往另一座城,
同时会挑战路线上武力值最高的K个骑士(Henry的体力有限,为了提高水平,当然要挑
战最强的骑士)。如果路线上的骑士不足K人,Henry会挑战遇到的所有人。
每次旅行前,可能会有某些骑士的武力值或定居地发生变化,Henry自然会打听消息,
并对计划做出调整。
为了在每次旅行时做好充分准备,Henry希望你能帮忙在每次旅行前计算出这条路线
上他将挑战哪些对手。


输入格式

第一行,一个整数N,表示有N座城,编号为1~N。
接下来N-1行,每行两个整数Ui和Vi,表示城Ui和城Vi之间有一条道路相连。
第N+1行,一个整数M,表示有M个骑士。
接下来M行,每行两个整数Fi和Pi。按顺序依次表示编号为1~M的每名骑士的武
力值和居住地。
第N+M+2行,两个整数Q,K,分别表示操作次数和每次旅行挑战的骑士数目上限。
接下来Q行,每行三个整数Ti,Xi,Yi。Ti取值范围为{1,2,3},表示操作类型。
一共有以下三种类型的操作:
Ti=1时表示一次旅行,Henry将从城Xi出发前往城市Yi;
Ti=2时表示编号为Xi的骑士的居住地搬到城Yi;
Ti=3时表示编号为Xi的骑士的武力值修正为Yi。


输出格式

输出若干行,依次为每个旅行的答案。
对每个Ti=1的询问,输出一行,按从大到小的顺序输出Henry在这次旅行中挑战的
所有骑士的武力值。如果路线上没有骑士,输出一行,为一个整数-1。


样例输入

5 
1 2 
1 3 
2 4 
2 5 
4 
10 1 
6 1 
14 5 
7 3 
5 3 
1 2 3 
1 5 3 
1 4 4 
2 1 4 
1 2 3 

样例输出

10 7 6 
14 10 7 
-1 
7 6 

提示

100%的数据中,1 ≤ N, M ≤ 40,000,1 ≤ Ui, Vi, Pi ≤ N,1 ≤ Q ≤ 80,000, 1 ≤ K ≤ 
20,旅行次数不超过 40,000 次,武力值为不超过1,000的正整数。 


题目来源

没有写明来源