Description：

给一棵树还有树上的 $k$ 条链，每条链都有权值，多次询问某一条链包含的所有链中权值第 $k$ 大的链。

$1\leqslant n\leqslant4\times 10^4$

Solution：

类似区间第 $k$ 大那样的做法，整体二分，唯一的问题就是给你 $x$ 条链如何快速判断它包含多少条链，这个可以用类似精神污染那道题的做法，用 $dfs$ 序转化以下条件就会发现 $dfn[a]$ 和 $dfn[b]$ 都是一个区间，所以会对一个二维空间中的矩形产生贡献，所以就用扫描线 $+$ 树状数组就可以矩形加，单点求值了，注意 $lca=a$ 时要特判，代码中为了方便可以使得 $a$ 永远是 $dfs$ 序较小的点，所以 $x$ 坐标的区间就应该小于 $y$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,mp,mq;

#define MAXN 80010

int b[MAXN],cnt = 0;

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void addedge(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dfn[MAXN],tot = 0,siz[MAXN],dep[MAXN];

int f[MAXN][17];

void dfs(int k,int depth)

{

	dep[k] = depth;

	dfn[k] = ++tot;siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			f[e[i].to][0] = k;

			dfs(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

		}

	}

	return;

}

struct chain

{

	int a,b,v,id;

}p[MAXN],p1[MAXN],p2[MAXN];

int ans[MAXN];

namespace CNT

{

	struct point

	{

		int x,y,id;

		bool operator < (const point& b)const

		{

			return x < b.x;

		}

	}t[MAXN];

	int pt = 0;

	struct query

	{

		int x,bot,top,type;

		bool operator < (const query &b)const

		{

			return x < b.x;

		}

	}q[MAXN * 2];

	int qnum = 0;

	int res[MAXN];

	int lowbit(int x){return x & (-x);}

	int c[MAXN];

	void add(int p,int x){for(int i = p;i <= n;i += lowbit(i))c[i] += x;return;}

	int calc(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

	void init(){qnum = 0;pt = 0;}

	void add_point(int x,int y,int id)

	{

		res[id] = 0;

		t[++pt] = (point){x,y,id};

		return;

	}

	void add_rect(int x1,int y1,int x2,int y2)

	{

		if(x1 > x2 || y1 > y2)return;

		q[++qnum] = (query){x1,y1,y2,1};q[++qnum] = (query){x2 + 1,y1,y2,-1};

		return;

	}

	void calc()

	{

		sort(t + 1,t + 1 + pt);sort(q + 1,q + 1 + qnum);

		int i,j;

		for(i = 1,j = 1;i <= pt;++i)

		{

			while(q[j].x <= t[i].x && j <= qnum)

			{

				add(q[j].bot,q[j].type);

				add(q[j].top + 1,-q[j].type);

				++j;

			}

			res[t[i].id] = calc(t[i].y);

		}

		for(--j;j >= 1;--j)

		{

			add(q[j].bot,-q[j].type);

			add(q[j].top + 1,q[j].type);

		}

		return;

	}

}

int LCA(int a,int b)

{

	if(dep[a] < dep[b])swap(a,b);

	for(int i = 16;i >= 0;--i)

		if(dep[f[a][i]] >= dep[b])a = f[a][i];

	if(a == b)return a;

	for(int i = 16;i >= 0;--i)

		if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];

	return f[a][0];

}

int skip_to_son(int k,int fa)

{

	for(int i = 16;i >= 0;--i)

		if(dep[f[k][i]] > dep[fa])k = f[k][i];

	return k;

}

void solve(int l,int r,int L,int R)

{

	if(L == R)

	{

		for(int i = l;i <= r;++i)if(p[i].id)ans[p[i].id] = L;

		return;

	}

	int mid = ((L + R) >> 1);

	int cnt1 = 0,cnt2 = 0;

	CNT::init();

	for(int i = l;i <= r;++i)

	{

		if(p[i].id != 0)

		{

			CNT::add_point(dfn[p[i].a],dfn[p[i].b],p[i].id);

		}

	}

	for(int i = l;i <= r;++i)

	{

		if(p[i].id == 0)

		{

			if(p[i].v <= mid)

			{

				int lca = LCA(p[i].a,p[i].b);

				if(lca == p[i].a)

				{

					int chi = skip_to_son(p[i].b,p[i].a);

					CNT::add_rect(1,dfn[p[i].b],dfn[chi] - 1,dfn[p[i].b] + siz[p[i].b] - 1);

					CNT::add_rect(dfn[p[i].b],dfn[chi] + siz[chi],dfn[p[i].b] + siz[p[i].b] - 1,n);

				}

				else

				{

					CNT::add_rect(dfn[p[i].a],dfn[p[i].b],dfn[p[i].a] + siz[p[i].a] - 1,dfn[p[i].b] + siz[p[i].b] - 1);

				}

				p1[++cnt1] = p[i];

			}

			else p2[++cnt2] = p[i];

		}

	}

	CNT::calc();

	for(int i = l;i <= r;++i)

	{

		if(p[i].id)

		{

			if(CNT::res[p[i].id] >= p[i].v)p1[++cnt1] = p[i];

			else{p[i].v -= CNT::res[p[i].id];p2[++cnt2] = p[i];}

		}

	}

	int cur = l;

	for(int i = 1;i <= cnt1;++i)p[cur++] = p1[i];

	for(int i = 1;i <= cnt2;++i)p[cur++] = p2[i];

	solve(l,l + cnt1 - 1,L,mid);

	solve(l + cnt1,r,mid + 1,R);

	return;

}

int main()

{

	scanf("%d%d%d",&n,&mp,&mq);

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

	dfs(1,1);

	for(int k = 1;k <= 16;++k)

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

			f[i][k] = f[f[i][k - 1]][k - 1];

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

	{

		p[i].a = rd();p[i].b = rd();

		p[i].v = rd();b[++cnt] = p[i].v;

		if(dfn[p[i].a] > dfn[p[i].b])swap(p[i].a,p[i].b);

	}

	sort(b + 1,b + 1 + cnt);

	cnt = unique(b + 1,b + 1 + cnt) - b - 1;

	for(int i = 1;i <= mp;++i)p[i].v = lower_bound(b + 1,b + 1 + cnt,p[i].v) - b;

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

	{

		p[i + mp].a = rd();p[i + mp].b = rd();

		p[i + mp].v = rd();p[i + mp].id = i;

		if(dfn[p[i + mp].a] > dfn[p[i + mp].b])swap(p[i + mp].a,p[i + mp].b);

	}

	solve(1,mp + mq,1,cnt);

	for(int i = 1;i <= mq;++i)printf("%d\n",b[ans[i]]);

	return 0;

}