题意：
给出一颗n个结点的树，点上有权值；
两种操作：
1.修改某个结点的权值；
2.求x,y路径上第K大值；
题解：
首先显然这题可以先树剖一下，将其转化为区间问题；
那么问题来了，用什么维护？
这是有很多办法的，一般人都会上一些比较显然的方法吧；
比如线段树套平衡树，二分答案处理询问；
时间达到了O(mlog^4n)。。。20*20*20*20=160000.。。；
空间比较好，O(nlogn)，这种方法是可以过的，但是我不想写平衡树，还不想要四个log；
那么区间第K大还有什么算法？划分树主席树！
那就上吧，树状数组log，，树链剖分log，线段树log；
三个log的复杂度比上一个优越一点，虽然空间降到了log^2n；
这样就可以解决此题了；
如果指针动态开内存会被卡内存的常，所以膜了一下大爷学习了一下内存池的开法就过了；
据说还有一种利用“入栈出栈序”来搞主席树可以是log^2n；
但是大多数人都是log^4算法30s卡过= =，我就不想学习那个了；
基本上没调，感觉这份代码应该写的还算不错0.0；
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 131072#define INF 100000000using namespace std;struct node{node *l,*r;int size;void* operator new (size_t);}*null=new node,*root[N],*st[512];void* node :: operator new (size_t){static node *mempool,*C;if(C==mempool)mempool=(C=new node[1<<16])+(1<<16);C->l=null;C->r=null;C->size=0;return C++;}int next[N<<1],to[N<<1],head[N],tot,val[N];int fa[N],ch[N],size[N],deep[N],top[N],p[N],cnt;int n,f[512],t;void init(){null->l=null->r=null;for(int i=1;i<=n;i++)root[i]=null;}inline void add(int x,int y){to[++tot]=y;next[tot]=head[x];head[x]=tot;}inline int lowbit(int x){return x&(-x);}void dfs1(int x,int pre){fa[x]=pre;deep[x]=deep[pre]+1;size[x]=1;int i,y;for(i=head[x];i;i=next[i]){if((y=to[i])!=pre){dfs1(y,x);size[x]+=size[y];if(size[ch[x]]<size[y])ch[x]=y;}}}void dfs2(int x,int t,int pre){top[x]=t;p[x]=++cnt;if(ch[x])dfs2(ch[x],t,x);int i,y;for(i=head[x];i;i=next[i]){if((y=to[i])!=pre&&y!=ch[x]){dfs2(y,y,x);}}}void Pushup(node* x){x->size=x->l->size+x->r->size;}void Insert(int l,int r,node* &x,int k,int val){if(x==null)x=new node;if(l==r){x->size+=val;return ;}int mid=l+r>>1;if(k<=mid)Insert(l,mid,x->l,k,val);else Insert(mid+1,r,x->r,k,val);Pushup(x);}int query(int l,int r,int k){if(l==r){if(k)return l;elsereturn -1;}int sum=0,mid=l+r>>1;for(int i=1;i<=t;i++)sum+=f[i]*st[i]->r->size;if(sum<k){for(int i=1;i<=t;i++)st[i]=st[i]->l;return query(l,mid,k-sum);}else{for(int i=1;i<=t;i++)st[i]=st[i]->r;return query(mid+1,r,k);}}void update(int p,int pre,int now){while(p<=n){Insert(0,INF,root[p],pre,-1);Insert(0,INF,root[p],now, 1);p+=lowbit(p);}}void Build(int n){for(int i=1;i<=n;i++){int temp=p[i];while(temp<=n){Insert(0,INF,root[temp],val[i],1);temp+=lowbit(temp);}}}void getroot(int x,int y){x–;while(x){st[++t]=root[x];f[t]=-1;x-=lowbit(x);}while(y){st[++t]=root[y];f[t]=1;y-=lowbit(y);}}int find(int x,int y,int k){t=0;int size=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);getroot(p[top[x]],p[x]);size+=p[x]-p[top[x]]+1;x=fa[top[x]];}if(deep[x]<deep[y])swap(x,y);getroot(p[y],p[x]);size+=p[x]-p[y]+1;if(k>size)return -1;return query(0,INF,k);}int main(){int m,i,j,k,x,y,v;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",val+i);for(i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y),add(y,x);}init();dfs1(1,0);dfs2(1,1,0);Build(n);for(i=1;i<=m;i++){scanf("%d",&k);if(k){scanf("%d%d",&x,&y);v=find(x,y,k);if(v==-1)puts("invalid request!");elseprintf("%d\n",v);}else{scanf("%d%d",&x,&v);update(p[x],val[x],v);val[x]=v;}}return 0;}
没有创造的生活不能算生活，只能算活着。
