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。

100%的数据中，1 ≤ N, M ≤ 40,000，1 ≤ Ui, Vi, Pi ≤ N，1 ≤ Q ≤ 80,000, 1 ≤ K ≤

20，旅行次数不超过 40,000 次，武力值为不超过1,000的正整数。

没有写明来源