[BJOI2015] 骑士的旅行
题目背景
在一片古老的土地上,有一个繁荣的文明。
这片大地几乎被森林覆盖,有N座城坐落其中。巧合的是,这N座城由恰好N-1条双向道路连接起来,使得任意两座城都是连通的。也就是说,这些城形成了树的结构,任意两座城之间有且仅有一条简单路径。
在这个文明中,骑士是尤其受到尊崇的职业。任何一名骑士,都是其家族乃至家乡的荣耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后,Henry终于满18岁了。他决定离开家乡,向那些成名已久的骑士们发起挑战!
题目描述
根据Henry的调查,大陆上一共有 $M$ 名受封骑士,不妨编号为 $1$ 到 $M$。第 $i$ 个骑士居住在城 $P_i$,武力值为 $F_i$。
Henry计划进行若干次旅行,每次从某座城出发沿着唯一的简单路径前往另一座城,同时会挑战路线上武力值最高的 $K$ 个骑士(Henry的体力有限,为了提高水平,当然要挑战最强的骑士)。如果路线上的骑士不足 $K$ 人,Henry会挑战遇到的所有人。
每次旅行前,可能会有某些骑士的武力值或定居地发生变化,Henry自然会打听消息,并对计划做出调整。
为了在每次旅行时做好充分准备,Henry希望你能帮忙在每次旅行前计算出这条路线上他将挑战哪些对手。
输入输出格式
输入格式
第一行,一个整数 $N$ ,表示有 $N$ 座城,编号为 $1 \sim N$。
接下来 $N-1$ 行,每行两个整数 $u_i$ 和 $v_i$,表示城 $u_i$ 和城 $v_i$ 之间有一条道路相连。
第 $N+1$ 行,一个整数 $M$,表示有 $M$ 个骑士。
接下来M行,每行两个整数 $F_i$ 和 $P_i$ 。按顺序依次表示编号为 $1 \sim M$ 的每名骑士的武力值和居住地。
第 $N+M+2$ 行,两个整数 $Q,~K$,分别表示操作次数和每次旅行挑战的骑士数目上限。
接下来 $Q$ 行,每行三个整数 $T_i,~X_i,~Y_i$ 。$T_i$ 取值范围为 $\{1,~2,~3\}$,表示操作类型。
一共有以下三种类型的操作:
$T_i=1$ 时表示一次旅行,Henry将从城 $X_i$ 出发前往城市 $Y_i$;
$T_i=2$ 时表示编号为 $X_i$ 的骑士的居住地搬到城 $Y_i$;
$T_i=3$ 时表示编号为 $X_i$ 的骑士的武力值修正为 $Y_i$。
输出格式
输出若干行,依次为每个旅行的答案。
对每个 $T_i=1$ 的询问,输出一行,按从大到小的顺序输出Henry在这次旅行中挑战的
所有骑士的武力值。如果路线上没有骑士,输出一行,为一个整数 $-1$。
输入输出样例
输入样例 #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
输出样例 #1
10 7 6
14 10 7
-1
7 6
说明
100%的数据中,$1 \leq N,~M \leq 40,000,~1 \leq Ui,~Vi,~Pi \leq N,~1\leq Q \leq 80,000,~1 \leq K \leq 20$,旅行次数不超过 40,000 次,武力值为不超过1,000的正整数。