我的思路大致是这样的 :

1. 二分 变为 $\pm 1$
2. 点分治
3. 统计跨 $u$ 节点的答案时使用单调队列
4. 如果之前子树深度最大为 $l_1$ , 我的子树深度最大为 $l_2$ , 那么单次操作复杂度数 $O( l_1 + l_2)$
5. 按照 $l$ 排序就可以让总复杂度变成 $O(\sum l_i)=O(sze_u)$
6. 这样复杂度就变成了 $O(n \log^2 n)$

求助哪里有问题 ? 思路有问题还是人傻常数大 ?

代码 :

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,l,r,flg[MAXN]; vector<pair<int,int>> G[MAXN];
int pre[MAXN],sze[MAXN],mx[MAXN],dep[MAXN];
void dfs1(int u,int f) {
	sze[u]=1,mx[u]=0;
	for(auto pr:G[u]) {
		int to=pr.first,w=pr.second;
		if(to==f||flg[to]) continue;
		dfs1(to,u);
		sze[u]+=sze[to],mx[u]=max(mx[u],mx[to]);
	}
	return ;
}
void dfs3(int u,int f) {
	dep[u]=dep[f]+1,mx[u]=dep[u];
	for(auto pr:G[u]) {
		int to=pr.first,w=pr.second;
		if(to==f||flg[to]) continue;
		dfs3(to,u);
		mx[u]=max(mx[u],mx[to]);
	}
	return ;
}
void find_core(int u,int f,int tot,int &core) {
	if(max(mx[u],tot-sze[u])<=tot/2) return core=u,void();
	for(auto pr:G[u]) {
		int to=pr.first,w=pr.second;
		if(to==f||flg[to]) continue;
		find_core(to,u,tot,core);
	}
	return ;
}
int L,R,len1,len2,arr[MAXN],Arr[MAXN],id[MAXN],Id[MAXN];
void dfs2(int u,int f,int& depmax,int W) {
	dep[u]=dep[f]+1,depmax=max(depmax,dep[u]);
	if(pre[u]>Arr[dep[u]]) Arr[dep[u]]=pre[u],Id[dep[u]]=u;
	for(auto pr:G[u]) {
		int to=pr.first,w=pr.second;
		if(to==f||flg[to]) continue;
		pre[to]=pre[u]+((w>=W)?1:-1);
		dfs2(to,u,depmax,W);
	}
	return ;
}
int que[MAXN],s,t;
void add(int id) {
	while(s<=t) {
		if(arr[id]>=arr[que[t]]) t--;
		else break;		
	}	
	que[++t]=id;
	return ;
}
void solve(void) {
	s=1,t=0;
	ffor(i,max(0,l-len2),min(len1,r-len2-1)) add(i);
	roff(i,len2,1) {
		if(r-i>=0&&r-i<=len1) add(r-i);
		while(s<=t&&que[s]<l-i) s++;
		if(s<=t) if(arr[que[s]]+Arr[i]>=0) L=id[que[s]],R=Id[i];	
	}
	return ;
}
void Divide_and_Solve(int u,int W) {
	dfs1(u,0); int core=-1; find_core(u,0,sze[u],core); u=core; assert(u>0);
	len1=0,len2=0;
	arr[len1]=0,id[len1]=u,dep[u]=0,pre[u]=0;
	vector<pair<int,pair<int,int>>> sons;
	dfs3(u,0); dep[u]=0;
	for(auto pr:G[u]) {
		int to=pr.first,w=pr.second;
		if(flg[to]) continue;
		sons.push_back({mx[to],{to,w}});
	}
	sort(sons.begin(),sons.end());
	for(auto pr:sons) {
		int to=pr.second.first,w=pr.second.second;
		pre[to]=((w>=W)?1:-1);
		dfs2(to,u,len2,W);
		solve();
		len1=max(len1,len2);
		ffor(i,1,len2) if(Arr[i]>arr[i]) arr[i]=Arr[i],id[i]=Id[i];
		ffor(i,1,len2) Arr[i]=-0x3f3f3f3f;
		len2=0;
	}
	ffor(i,0,len1) arr[i]=-0x3f3f3f3f;
	len1=0,len2=0;
	flg[u]=1;
	for(auto pr:G[u]) {
		int to=pr.first;
		if(flg[to]) continue;
		Divide_and_Solve(to,W);
	}
	return ;
}
pair<int,pair<int,int>> check(int w) { //ge w 的边将被赋予 +1 < w 的边将被赋予 -1 
	L=-1,R=-1; ffor(i,1,n) flg[i]=0;
	Divide_and_Solve(1,w);
	if(L==-1) return {0,{0,0}};
	return {1,{L,R}};
}
pair<int,int> bfind(int l,int r) {
	int ansl=-1,ansr=-1;
	while(l<=r) {
		int mid=l+r>>1;
		auto pr=check(mid);
		if(pr.first) ansl=pr.second.first,ansr=pr.second.second,l=mid+1;
		else r=mid-1;
	}
	return {ansl,ansr};
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>l>>r; memset(arr,-0x3f,sizeof(arr)),memset(Arr,-0x3f,sizeof(Arr));
	int r0=-INT_MAX,l0=INT_MAX;
	ffor(i,1,n-1) {
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w}),G[v].push_back({u,w});	
		l0=min(l0,w),r0=max(r0,w);
	}
	auto pr=bfind(l0,r0);
	cout<<pr.first<<' '<<pr.second;
	return 0;
}