#1470. BJOI2015 骑士的旅行

BJOI2015 骑士的旅行

Description

在一片古老的土地上,有一个繁荣的文明。

这片大地几乎被森林覆盖,有N座城坐落其中。巧合的是,这N座城由恰好N-1条双

向道路连接起来,使得任意两座城都是连通的。也就是说,这些城形成了树的结构,任意两

座城之间有且仅有一条简单路径。

在这个文明中,骑士是尤其受到尊崇的职业。任何一名骑士,都是其家族乃至家乡的荣

耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后,Henry

终于满18岁了。他决定离开家乡,向那些成名已久的骑士们发起挑战!

根据Henry的调查,大陆上一共有M名受封骑士,不妨编号为1到M。

第i个骑士居住在城Pi,武力值为Fi。

Henry计划进行若干次旅行,每次从某座城出发沿着唯一的简单路径前往另一座城,

同时会挑战路线上武力值最高的K个骑士(Henry的体力有限,为了提高水平,当然要挑

战最强的骑士)。如果路线上的骑士不足K人,Henry会挑战遇到的所有人。

每次旅行前,可能会有某些骑士的武力值或定居地发生变化,Henry自然会打听消息,

并对计划做出调整。

为了在每次旅行时做好充分准备,Henry希望你能帮忙在每次旅行前计算出这条路线

上他将挑战哪些对手。

Format

Input

第一行,一个整数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。

Output

输出若干行,依次为每个旅行的答案。

对每个Ti=1的询问,输出一行,按从大到小的顺序输出Henry在这次旅行中挑战的

所有骑士的武力值。如果路线上没有骑士,输出一行,为一个整数-1。

Samples

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

Limitation

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

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