由于$BZOJ$上经常有人拿这道题卡评测姬，所以变成了权限题。。。

本蒟蒻表示没钱氪金。。。

这里附上洛谷的体面：

题目描述

风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。

首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。

这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，权值为c_i。

接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第i 个水果是从顶点 u_i 到顶点v_i 的路径。

幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径（例如图1中从 3到7 的路径是从1到8的路径的子路径）。这里规定:从a 到b的路径与从b到 a的路径是同一条路径。

当然为了提高难度，对于第 i 个水果，你需要选择能接住它的所有盘子中，权值第 k_i 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？ 

输入输出格式

输入格式：

第一行三个数 n和P 和Q，表示树的大小和盘子的个数和水果的个数。 接下来n-1 行，每行两个数 a、b，表示树上的a和b 之间有一条边。树中顶点按1到 n标号。 接下来 P 行，每行三个数 a、b、c，表示路径为 a 到 b、权值为 c 的盘子，其中0<=c<=10^9，a不等于b。 接下来Q行，每行三个数 u、v、k，表示路径为 u到 v的水果，其中 u不等于v，你需要选择第 k小的盘子，第k 小一定存在。

输出格式：

对于每个果子，输出一行表示选择的盘子的权值。

输入输出样例

输入样例#1： 

10 10 101 22 33 44 55 66 77 88 99 103 2 21739443410 7 130222696 7 2832544856 8 3330423604 6 4421393728 3 22504559010 4 92220520910 8 8082963309 2 4863313614 9 5511763381 8 53 8 33 8 41 8 34 8 12 3 12 3 12 3 12 4 11 4 1

输出样例#1： 

442139372 333042360 442139372 283254485 283254485 217394434 217394434 217394434 217394434 217394434

说明

N,P,Q<=40000。

---

题解Here!

题目大意：给定一棵树和$m$条路径，每条路径有一个权值，$q$次询问，每次询问某条路经包含的所有路径中权值的第$k$小。

本蒟蒻表示并不会整体二分/CDQ分治。。。

所以怒写树链剖分+权值线段树套动态开点区间线段树然后$1A$。。。

然后我$4h$就搭上面了。。。

考虑满足什么条件的水果$(x_1,y_1)$会落在指定盘子$(x_2,y_2)$上：

如果$x_2,y_2$为祖先孩子关系，设$x_2$是$y_2$的祖先，$t$是$x_2$到$y_2$路径上第二个点，那么$x_1,y_1$一定满足$x_1$在$y_2$子树中，$y_1$在$x_2$子树外。 

盗一张图：

在子树中可以表示为$dfs$序中一段，在子树外可以表示为两段。

但是我为了偷点懒，直接写了个树链剖分。。。

否则$x_1$一定在$x_2$子树中，$y_1$一定在$y_2$子树中。

再盗一张图：

在我的程序里面$last[x]==id[x]+size[x]-1$

这样问题就转化成平面上一些矩形，每个矩形有权值，一些询问，求包含一个点的权值第$k$小的矩形。

离线下来，把一维的矩形坐标拆成在$x_1$处$+1$，$x_2+1$处$-1$。

排一下序。然后就变成了一个二维问题。

需要普通线段树维护位置，权值线段树维护第$K$大。

由于外层树结构不支持区间修改，因此需要权值线段树套区间线段树。

所以总复杂度为$O(n\log_2^2n)$。

附代码：（一大堆为了调试而自造的分隔符。。。）

#include
     
      #include
      
       #include
       
        #define MAXN 40010using namespace std;//----------------------------------------------------------------------------------------------------int n,m,q,num=0,c=1,d=1,num_plate=0;int head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],id[MAXN],pos[MAXN],top[MAXN];int root[MAXN<<2],lsh[MAXN],ans[MAXN];//----------------------------------------------------------------------------------------------------struct Tree{	int next,to;}edge[MAXN<<1];//----------------------------------------------------------------------------------------------------struct Plate{	int x,l,r,val,c;	friend bool operator <(const Plate &p,const Plate &q){		if(p.x==q.x)return p.c>q.c;		return p.x
        
         '9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}//----------------------------------------------------------------------------------------------------namespace ST{	#define DATA(x) a[x].data	#define LSIDE(x) a[x].lson	#define RSIDE(x) a[x].rson	int size=0;	struct Segment_Tree{		int data,lson,rson;	}a[MAXN*500];	void insert(int l,int r,int c,int lside,int rside,int &rt){		if(!rt)rt=++size;		if(l<=lside&&rside<=r){			DATA(rt)+=c;			return;		}		int mid=lside+rside>>1;		if(l<=mid)insert(l,r,c,lside,mid,LSIDE(rt));		if(mid
         
          >1,ans=DATA(rt);		if(l<=mid)ans+=query(l,r,lside,mid,LSIDE(rt));		if(mid
          
           >1; if(v<=mid)insert(k,v,l,mid,LSON); else insert(k,v,mid+1,r,RSON); } int query(int k,int v,int l,int r,int rt){ if(l==r)return lsh[l]; int mid=l+r>>1,t=ST::query(v,v,1,n,root[LSON]); if(k<=t)return query(k,v,l,mid,LSON); else return query(k-t,v,mid+1,r,RSON); }}//----------------------------------------------------------------------------------------------------inline void add_edge(int x,int y){ edge[c].to=y;edge[c].next=head[x];head[x]=c++; edge[c].to=x;edge[c].next=head[y];head[y]=c++;}inline void new_plate(int l1,int r1,int l2,int r2,int val){ num_plate++; plate[num_plate].x=l1;plate[num_plate].l=l2;plate[num_plate].r=r2;plate[num_plate].val=val; plate[num_plate].c=1; //-------------------------------------------------------------------------------- num_plate++; plate[num_plate].x=r1+1;plate[num_plate].l=l2;plate[num_plate].r=r2;plate[num_plate].val=val; plate[num_plate].c=-1;}inline void add_plate(int l1,int r1,int l2,int r2,int val){ new_plate(l1,r1,l2,r2,val); new_plate(l2,r2,l1,r1,val);}inline void add_que(int l,int r,int k,int i){ que[i].l=l;que[i].r=r;que[i].k=k; que[i].id=i;}//----------------------------------------------------------------------------------------------------void dfs1(int rt){ son[rt]=0;size[rt]=1; for(int i=head[rt];i;i=edge[i].next){ int will=edge[i].to; if(!deep[will]){ deep[will]=deep[rt]+1; fa[will]=rt; dfs1(will); size[rt]+=size[will]; if(size[son[rt]]
           
            deep[x]){ if(fa[top[y]]==x)return top[y]; y=fa[top[y]]; } return son[x];}//----------------------------------------------------------------------------------------------------void work(){ for(int i=1,now=1;i<=q;i++){ while(now<=num_plate&&plate[now].x<=que[i].l){ CT::insert(now,plate[now].val,1,num,1); now++; } ans[que[i].id]=CT::query(que[i].k,que[i].r,1,num,1); } for(int i=1;i<=q;i++)printf("%d\n",ans[i]);}//----------------------------------------------------------------------------------------------------void init(){ int u,v,w; n=read();m=read();q=read(); for(int i=1;i
            
             deep[v])swap(u,v); if(id[u]<=id[v]&&id[v]+size[v]<=id[u]+size[u]){ int x=subtree(u,v); if(id[x]>1)add_plate(id[v],id[v]+size[v]-1,1,id[x]-1,w); if(id[x]+size[x]<=n)add_plate(id[v],id[v]+size[v]-1,id[x]+size[x],n,w); } else add_plate(id[u],id[u]+size[u]-1,id[v],id[v]+size[v]-1,w); } sort(lsh+1,lsh+num+1); num=unique(lsh+1,lsh+num+1)-lsh-1; for(int i=1;i<=num_plate;i++)plate[i].val=lower_bound(lsh+1,lsh+num+1,plate[i].val)-lsh; sort(plate+1,plate+num_plate+1); //-------------------------------------------------------------------------------- for(int i=1;i<=q;i++){ u=read();v=read();w=read(); if(deep[u]>deep[v])swap(u,v); add_que(id[u],id[v],w,i); } sort(que+1,que+q+1);}//----------------------------------------------------------------------------------------------------int main(){ init(); work(); return 0;}