风见幽香非常喜欢玩一个叫做 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 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？

因为预先做过，不难想到对于树上路径的处理方法和它一样。

那么对于每个盘子用dfs序表示的路径点(u,v)，分两种情况：

1.u和v有一个不同于二者的lca

显然它能接到的水果的两端一个在u的子树中，一个在v的子树中。

2.v是u的祖先。

显然它能接到的水果的两端一个在u的子树中，一个在v的子树的补集（包括v）中。

那么对于一个水果的路径点，如果在这个矩形当中，就说明这个水果能够被哪些盘子所接。

那么处理完之后，显然不能用主席树来解决第k大（如果能当我没说），于是我们整体二分一下即可。

……这是我最开始做这道题的想法，但是码了4h后对此绝望，对着数据参着题解调到现在才过。

说几个（我）容易错的点：

1.区间第k小，所以不是第k大的做法，注意答案在左区间还是右区间。

2.用扫描线存的时候注意空间开大点，另外上边界不要忘了+1

3.矩形的x和y坐标以及水果的x和y坐标存法（顺序）一定要相同。

代码138行凑和吧，但是细节真心多。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;const int N=4e4+5;const int B=17;inline int read(){    int X=0,w=0;char ch=0;    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();    return w?-X:X;}struct path{    int to,nxt;}e[N*2];struct dish{    int x1,x2,y,c,w;}d[4*N],td1[4*N],td2[4*N];struct fruit{    int x,y,k,id;}f[N],tf1[N],tf2[N];int m,b[N],ans[N],tr[N],c[N];int anc[N][B+4],dep[N],size[N];int n,p,q,cnt,head[N],pos[N],tot;inline bool cmp1(dish a,dish b){    return a.y
          
           =0;--k) if(dep[anc[i][k]]>=dep[j])i=anc[i][k]; if(i==j)return i; for(int k=B;k>=0;--k) if(anc[i][k]!=anc[j][k]) i=anc[i][k],j=anc[j][k]; return anc[i][0];}inline int lowbit(int t){ return t&(-t);}inline void ins(int x,int y){ for(int i=x;i<=n;i+=lowbit(i))tr[i]+=y;}inline int qry(int x){ int res=0; for(int i=x;i;i-=lowbit(i))res+=tr[i]; return res;}inline void mdy(int l,int r,int w){ ins(l,w);ins(r+1,-w);}void solve(int L,int R,int s,int t,int l,int r){ if(L>R||s>t)return; if(l==r){ for(int i=L;i<=R;++i)ans[f[i].id]=c[l]; return; } int id1=0,id2=0,if1=0,if2=0,mid=(l+r)>>1,j=s; for(int i=L;i<=R;++i){ for(;j<=t&&d[j].y<=f[i].y;++j){ if(d[j].c>c[mid])td1[id1++]=d[j]; else mdy(d[j].x1,d[j].x2,d[j].w),td2[id2++]=d[j]; } int tmp=qry(f[i].x); if(f[i].k>tmp)f[i].k-=tmp,tf1[if1++]=f[i]; else tf2[if2++]=f[i]; } for(;j<=t;++j){ if(d[j].c>c[mid])td1[id1++]=d[j]; else mdy(d[j].x1,d[j].x2,d[j].w),td2[id2++]=d[j]; } int mdst=s+id1,MID=L+if1; for(int i=s;i
           
            pos[v])swap(u,v); int lca=LCA(u,v); if(lca!=u&&lca!=v){ d[++m]=(dish){pos[u],pos[u]+size[u]-1,pos[v],c[i],1}; d[++m]=(dish){pos[u],pos[u]+size[u]-1,pos[v]+size[v],c[i],-1}; }else{ int t=v; for(int k=B;k>=0;--k) if(dep[anc[t][k]]>=dep[u]+1)t=anc[t][k]; d[++m]=(dish){ 1,pos[t]-1,pos[v],c[i],1}; d[++m]=(dish){ 1,pos[t]-1,pos[v]+size[v],c[i],-1}; d[++m]=(dish){pos[v],pos[v]+size[v]-1,pos[t]+size[t],c[i],1}; d[++m]=(dish){pos[v],pos[v]+size[v]-1,n+1,c[i],-1}; } } for(int i=1;i<=q;++i){ int u=read(),v=read(),k=read(); if(pos[u]>pos[v])swap(u,v); f[i]=(fruit){pos[u],pos[v],k,i}; } sort(d+1,d+m+1,cmp1); sort(f+1,f+q+1,cmp2); sort(c+1,c+p+1); int len=unique(c+1,c+p+1)-c-1; solve(1,q,1,m,1,len); for(int i=1;i<=q;++i)printf("%d\n",ans[i]); return 0;}
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++