题目：
Description
在一片古老的土地上，有一个繁荣的文明。
这片大地几乎被森林覆盖，有N座城坐落其中。巧合的是，这N座城由恰好N-1条双
向道路连接起来，使得任意两座城都是连通的。也就是说，这些城形成了树的结构，任意两
座城之间有且仅有一条简单路径。
在这个文明中，骑士是尤其受到尊崇的职业。任何一名骑士，都是其家族乃至家乡的荣
耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后，Henry
终于满18岁了。他决定离开家乡，向那些成名已久的骑士们发起挑战！
根据Henry的调查，大陆上一共有M名受封骑士，不妨编号为1到M。
第i个骑士居住在城Pi，武力值为Fi。
Henry计划进行若干次旅行，每次从某座城出发沿着唯一的简单路径前往另一座城，
同时会挑战路线上武力值最高的K个骑士（Henry的体力有限，为了提高水平，当然要挑
战最强的骑士）。如果路线上的骑士不足K人，Henry会挑战遇到的所有人。
每次旅行前，可能会有某些骑士的武力值或定居地发生变化，Henry自然会打听消息，
并对计划做出调整。
为了在每次旅行时做好充分准备，Henry希望你能帮忙在每次旅行前计算出这条路线
上他将挑战哪些对手。
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。
Sample Input
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 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
Sample Output
10 7 6
14 10 7
-1
7 6
14 10 7
-1
7 6
Hint
100%的数据中，1 ≤ N, M ≤ 40,000，1 ≤ Ui, Vi, Pi ≤ N，1 ≤ Q ≤ 80,000, 1 ≤ K ≤
20，旅行次数不超过 40,000 次，武力值为不超过1,000的正整数。
题解：
先树链剖分····然后树链剖分的每一个树上套上一颗权值线段树····
我的方法有点暴力···要输入前K大直接一个一个找·····所以慢得飞起·····
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=4e5+;
const int M=4e7+;
struct node
{
int size,l,r;
}tr[M];
int n,m,q,K;
int tot,fst[N],nxt[N*],go[N*],f[N],p[N],root[N*],loc[N*],cnt,sum[N*],temp,que[N*];
int father[N],deep[N],son[N],size[N],pos[N],idx[N],top[N];
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar())
f=(f<<)+(f<<)+c-'';
return f;
}
inline void comb(int a,int b)
{
nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b;
nxt[++tot]=fst[b],fst[b]=tot,go[tot]=a;
}
inline void dfs1(int u)
{
size[u]=;
for(int e=fst[u];e;e=nxt[e])
{
int v=go[e];if(v==father[u]) continue;
father[v]=u;deep[v]=deep[u]+;
dfs1(v);size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
inline void dfs2(int u)
{
if(son[u])
{
idx[pos[son[u]]=++tot]=son[u];
top[son[u]]=top[u];dfs2(son[u]);
}
for(int e=fst[u];e;e=nxt[e])
{
int v=go[e];if(v==father[u]||v==son[u]) continue;
idx[pos[v]=++tot]=v;
top[v]=v;dfs2(v);
}
}
inline void pre()
{
dfs1();
tot=pos[]=idx[]=top[]=;
dfs2();
}
inline void modify2(int &k,int l,int r,int v)
{
if(!k) k=++tot;tr[k].size++;
if(l==r) return;
int mid=(l+r)/;
if(v<=mid) modify2(tr[k].l,l,mid,v);
else modify2(tr[k].r,mid+,r,v);
}
inline void delete2(int k,int l,int r,int v)
{
tr[k].size--;
if(l==r) return;
int mid=(l+r)/;
if(v<=mid) delete2(tr[k].l,l,mid,v);
else delete2(tr[k].r,mid+,r,v);
}
inline void modify1(int k,int l,int r,int p,int v)
{
sum[k]++;
modify2(root[k],,,v);
if(l==r) return;
int mid=(l+r)/;
if(p<=mid) modify1(k*,l,mid,p,v);
else modify1(k*+,mid+,r,p,v);
}
inline void delete1(int k,int l,int r,int p,int v)
{
sum[k]--;
delete2(root[k],,,v);
if(l==r) return;
int mid=(l+r)/;
if(p<=mid) delete1(k*,l,mid,p,v);
else delete1(k*+,mid+,r,p,v);
}
inline void getroot2(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
que[++cnt]=root[k];temp+=sum[k];
return;
}
int mid=(l+r)/;
if(x<=mid) getroot2(k*,l,mid,x,y);
if(y>mid) getroot2(k*+,mid+,r,x,y);
}
inline void getroot1(int a,int b)
{
if(top[a]!=top[b])
{
if(deep[top[a]]<deep[top[b]]) swap(a,b);
getroot2(,,n,pos[top[a]],pos[a]);
getroot1(father[top[a]],b);
}
else
{
if(deep[a]<deep[b]) swap(a,b);
getroot2(,,n,pos[b],pos[a]);
}
}
inline int calc()
{
int t=;
for(int i=;i<=cnt;i++) t+=tr[tr[loc[i]].l].size;
return t;
}
inline void trans(int op)
{
if(!op)
for(int i=;i<=cnt;i++) loc[i]=tr[loc[i]].l;
else
for(int i=;i<=cnt;i++) loc[i]=tr[loc[i]].r;
}
inline int query(int l,int r,int k)
{
if(l==r) return l;
int t=calc();int mid=(l+r)/;
if(t>=k)
{
trans();
return query(l,mid,k);
}
else
{
trans();
return query(mid+,r,k-t);
}
}
int main()
{
n=R();int a,b,op;
for(int i=;i<n;i++)
{
a=R(),b=R();
comb(a,b);
}
pre();
m=R();tot=;
for(int i=;i<=m;i++)
{
f[i]=R(),p[i]=R();
modify1(,,n,pos[p[i]],f[i]);
}
q=R(),K=R();
while(q--)
{
op=R(),a=R(),b=R();
if(op==)
{
temp=cnt=;
getroot1(a,b);
if(!temp) printf("-1");
if(temp<=K)
{
for(int i=temp;i>=;i--)
{
for(int j=;j<=cnt;j++) loc[j]=que[j];
printf("%d ",query(,,i));
}
}
else
{
for(int i=temp;i>=temp-K+;i--)
{
for(int j=;j<=cnt;j++) loc[j]=que[j];
printf("%d ",query(,,i));
}
}
printf("\n");
}
else if(op==)
{
delete1(,,n,pos[p[a]],f[a]);
p[a]=b;
modify1(,,n,pos[p[a]],f[a]);
}
else if(op==)
{
delete1(,,n,pos[p[a]],f[a]);
f[a]=b;
modify1(,,n,pos[p[a]],f[a]);
}
}
}