传送门

其实这题难点在于处理路径包含关系

先求出树的dfn序,现在假设路径\(xy\)包含\(uv(dfn_x<dfn_y,dfn_u<dfn_v)\)

• 如果\(lca(u,v)!=u\),那么\(x,y\)要分别在\(u,v\)子树中,即\(dfn_u\le dfn_x\le dfn_u+sz_u-1,dfn_v\le dfn_y\le dfn_v+sz_v-1\)

• 如果\(lca(u,v)=u\),设\(uv\)链上\(u\)的下一个点为\(w\),那么\(x,y\)一个在\(w\)子树外,一个在\(v\)子树内,即\(1\le dfn_x\le dfn_w-1,dfn_v\le dfn_y\le dfn_v+sz_v-1\)或\(dfn_v\le dfn_x\le dfn_v+sz_v-1,dfn_w+sz_w\le dfn_x\le n\)

然后把\(dfn_x,dfn_y\)看成一个点,所以一条路径的子路径条数就是那个点被多少矩形覆盖,矩形覆盖可以扫描线解决

因为多组询问+可以离线,所以套个整体二分求第k小就好了

#include<bits/stdc++.h>

#define LL long long

#define db double

#define il inline

#define re register

using namespace std;

const int N=40000+10;

il int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int to[N<<1],nt[N<<1],hd[N],tot;

il void add(int x,int y)

{

    ++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;

    ++tot,to[tot]=x,nt[tot]=hd[y],hd[y]=tot;

}

int fa[N],sz[N],de[N],hs[N],top[N],dfn[N],pp[N],ti;

void dfs1(int x)

{

    sz[x]=1;

    for(int i=hd[x];i;i=nt[i])

    {

        int y=to[i];

        if(y==fa[x]) continue;

        fa[y]=x,de[y]=de[x]+1,dfs1(y),sz[x]+=sz[y];

        hs[x]=sz[hs[x]]>sz[y]?hs[x]:y;

    }

}

void dfs2(int x,int ntp)

{

    dfn[x]=++ti,pp[ti]=x,top[x]=ntp;

    if(hs[x]) dfs2(hs[x],ntp);

    for(int i=hd[x];i;i=nt[i])

    {

        int y=to[i];

        if(y!=fa[x]&&y!=hs[x]) dfs2(y,y);

    }

}

int glca(int x,int y)

{

    while(top[x]!=top[y])

    {

        if(de[top[x]]<de[top[y]]) swap(x,y);

        x=fa[top[x]];

    }

    return de[x]<de[y]?x:y;

}

int n,m,tt,q,an[N],c[N];

void ad(int x,int y){if(!x) return;while(x<=n) c[x]+=y,x+=x&(-x);}

int gsm(int x){int an=0;while(x) an+=c[x],x-=x&(-x);return an;}

struct md

{

    int x,l,r,z,k;

    bool operator < (const md &bb) const {return x<bb.x;}

}mm[N<<2],lmm[N<<2],rmm[N<<2];

struct qu

{

    int x,y,k,i;

    bool operator < (const qu &bb) const {return x<bb.x;}

}qq[N],lq[N],rq[N];

void dc(int l,int r,int ll,int rr,int lx,int rx)

{

    if(l>r||ll>rr) return;

    if(lx==rx)

    {

        for(int i=ll;i<=rr;++i) an[qq[i].i]=lx;

        return;

    }

    int mid=(lx+rx)>>1;

    int tl1=0,tr1=0,tl2=0,tr2=0,i=l,j=ll;

    while(i<=r||j<=rr)

    {

        if(j>rr||(i<=r&&mm[i].x<=qq[j].x))

        {

            if(mm[i].z<=mid) lmm[++tl1]=mm[i],ad(mm[i].l,mm[i].k),ad(mm[i].r+1,-mm[i].k);

            else rmm[++tr1]=mm[i];

            ++i;

        }

        else

        {

            int cn=gsm(qq[j].y);

            if(cn>=qq[j].k) lq[++tl2]=qq[j];

            else qq[j].k-=cn,rq[++tr2]=qq[j];

            ++j;

        }

    }

    for(int i=1;i<=tl1;++i) mm[l+i-1]=lmm[i],ad(lmm[i].l,-lmm[i].k),ad(lmm[i].r+1,lmm[i].k);

    for(int i=1;i<=tr1;++i) mm[l+tl1+i-1]=rmm[i];

    for(int i=1;i<=tl2;++i) qq[ll+i-1]=lq[i];

    for(int i=1;i<=tr2;++i) qq[ll+tl2+i-1]=rq[i];

    dc(l,l+tl1-1,ll,ll+tl2-1,lx,mid),dc(l+tl1,r,ll+tl2,rr,mid+1,rx);

}

int main()

{

    n=rd(),m=rd(),q=rd();

    for(int i=1;i<n;++i) add(rd(),rd());

    dfs1(1),dfs2(1,1);

    for(int i=1;i<=m;++i)

    {

        int x=rd(),y=rd(),z=rd();

        if(dfn[x]>dfn[y]) swap(x,y);

        int lca=glca(x,y);

        if(lca!=x) mm[++tt]=(md){dfn[x],dfn[y],dfn[y]+sz[y]-1,z,1},mm[++tt]=(md){dfn[x]+sz[x],dfn[y],dfn[y]+sz[y]-1,z,-1};

        else

        {

            int xx=y,la;

            while(top[x]!=top[xx]) la=top[xx],xx=fa[top[xx]];

            xx=xx!=x?pp[dfn[x]+1]:la;

            mm[++tt]=(md){1,dfn[y],dfn[y]+sz[y]-1,z,1},mm[++tt]=(md){dfn[xx],dfn[y],dfn[y]+sz[y]-1,z,-1};

            mm[++tt]=(md){dfn[y],dfn[xx]+sz[xx],n,z,1},mm[++tt]=(md){dfn[y]+sz[y],dfn[xx]+sz[xx],n,z,-1};

        }

    }

    sort(mm+1,mm+tt+1);

    while(mm[tt].x>n) --tt;

    for(int i=1;i<=q;++i)

    {

        int x=rd(),y=rd(),k=rd();

        if(dfn[x]>dfn[y]) swap(x,y);

        qq[i]=(qu){dfn[x],dfn[y],k,i};

    }

    sort(qq+1,qq+q+1);

    dc(1,tt,1,q,0,1<<30);

    for(int i=1;i<=q;++i) printf("%d\n",an[i]);

    return 0;

}