Description：

给定一颗带边权的树，求一条边数在 $[L,R]$ 之间的路径，使得路径上边权的中位数最大。

$1\leqslant n\leqslant 10^5$

Solution：

首先二分答案，把 $\geqslant ans$ 的边权值设成 $1$ ，其他边权值设成 $-1$ ，问题就变成了判断是否存在一条路径权值和 $\geqslant 0$ 。

看着这种限制路径长度的问题，不难想到点分治，但是会发现朴素的点分治复杂度不对。

那么我们就在点分治的时候，先求出每一个点分子树中深度为 $k$ 时的最大值，然后每次查询 $[L-k,R-k]$ 的最大值，不难发现可以用单调队列来优化滑动窗口最值，每次单调队列初始化的时候只用初始化 $[L-maxdep,R-maxdep-1]\cup [1,maxdep]$ 这部分即可，会发现初始化的大小与他之前的子树的最大深度有关，因此把所有子树排序，这样每次 $maxdep$ 不会超过子树大小，复杂度就是对的了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,l,r;

#define MAXN 100010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

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

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

	return;

}

#define INF 0x3f3f3f3f

int sum,root,siz[MAXN],d[MAXN];

bool vis[MAXN];

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

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

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

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

		d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],sum - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

vector<int> v[MAXN];

bool cmp(int a,int b){return siz[a] < siz[b];}

int rt;

void divide(int k)

{

	vis[k] = true;

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

	{

		if(vis[e[i].to])continue;

		root = 0;sum = siz[e[i].to];

		getroot(e[i].to,0);

		v[k].push_back(root);

	}

	getroot(k,0);

	sort(v[k].begin(),v[k].end(),cmp);

	for(vector<int>::iterator it = v[k].begin();it != v[k].end();++it)

	{

		divide(*it);

	}

	vis[k] = false;

	return;

}

int mx = 0;

int t[MAXN],p[MAXN];

int s[MAXN],g[MAXN];

int depth = 0;

void dfs(int k,int fa,int dep,int val,int w)

{

	depth = max(depth,dep);

	if(val > s[dep])

	{

		s[dep] = val;

		g[dep] = k;

	}

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

	{

		if(!vis[e[i].to] && e[i].to != fa)

		{

			dfs(e[i].to,k,dep + 1,val + (e[i].v >= w ? 1 : -1),w);

		}

	}

	return;

}

int q[MAXN],head,tail;

#define NEG 0xc0c0c0c0

int ans1,ans2;

void calc(int k,int w)

{

	t[0] = 0;p[0] = k;

	int maxdep = 0;

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

	{

		if(vis[e[i].to])continue;

		depth = 0;

		dfs(e[i].to,0,1,(e[i].v >= w ? 1 : -1),w);

		head = 0;tail = -1;

		depth = min(depth,r);

		for(int i = max(l - depth,0);i < r - depth && i <= maxdep;++i)

		{

			while(head <= tail && t[i] >= t[q[tail]])--tail;

			q[++tail] = i;

		}

		for(int i = depth;i >= 1;--i)

		{

			while(head <= tail && q[head] < l - i)++head;

			while(head <= tail && t[r - i] >= t[q[tail]])--tail;

			q[++tail] = r - i;

			if(head <= tail)

			{

				if(t[q[head]] + s[i] > mx)

				{

					mx = t[q[head]] + s[i];

					ans1 = p[q[head]];ans2 = g[i];

				}

			}

		}

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

		{

			if(s[i] > t[i])

			{

				t[i] = s[i];

				p[i] = g[i];

			}

		}

		maxdep = max(maxdep,depth);

		for(int i = 1;i <= depth;++i)s[i] = NEG;

	}

	for(int i = 1;i <= maxdep;++i)t[i] = NEG;

	return;

}

void work(int k,int w)

{

	vis[k] = true;

	calc(k,w);

	for(vector<int>::iterator it = v[k].begin();it != v[k].end();++it)

	{

		work(*it,w);

	}

	vis[k] = false;

	return;

}

bool check(int v)

{

	mx = -INF;

	work(rt,v);

	return (mx >= 0);

}

int main()

{

	memset(t,0xc0,sizeof(t));

	memset(s,0xc0,sizeof(s));

	scanf("%d%d%d",&n,&l,&r);

	int a,b,c;

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

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	sum = n;root = 0;d[0] = INF;

	getroot(1,0);

	rt = root;

	divide(root);

	int l = 0,r = 1000000000,mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(check(mid))l = mid;

		else r = mid - 1;

	}

	check(l);

	cout << ans1 << " " << ans2 << endl;

	return 0;

}