好久不见哎

退役不成还是来逛一圈辣QAQ

树分治没怎么好好写过QAQ

是时候好好练练辣。~

感觉写起来还是挺有套路的呀。

大都是考虑过某个子树根节点的路径等来进行求解吧。

不断地找重心->分治

（代码总是调得要死要死的TAT）

BZOJ：

BZOJ-1095: [ZJOI2007]Hide 捉迷藏

动态树分治

按重心弄一棵新树QAQ

然后我们每个节点开两个堆

第一个堆记子树中所有节点到父亲节点的距离

第二个堆记所有子节点的堆顶

那么一个节点的第二个堆中的最大值和次大值加起来就是子树中经过这个节点的最长链

然后我们最后开一个全局的堆，记录所有第二个堆中最大值和次大值之和

那么全局的堆顶就是答案

Bingo~

（一个怎么都（没）不（时）想（间）手写堆的傻逼选手在NOIP赛场上各种姿势被卡）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;
const int NN = 100005,INF = 0x3f3f3f3f;
int bin[20],LOG[NN<<1],n,m,rt,tot,cnt,tott,sum,mn[18][NN<<1];
int pos[NN],fa[NN],sz[NN],f[NN],deep[NN],head[NN];
bool vis[NN],num[NN];
struct E
{
	int ne,v;
}e[NN<<1];
void Build(int xx,int yy)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
	e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx;
}
struct H
{
	priority_queue <int> qa,qb;
	void ps(int xx) { qa.push(xx); }
	void er(int xx) { qb.push(xx); }
	void pp()
	{
		while (qb.size() && qa.top() == qb.top()) qa.pop(), qb.pop();
		qa.pop();
	}
	int tp()
	{
		while (qb.size() && qa.top() == qb.top()) qa.pop(), qb.pop();
		if (!qa.size()) return 0;
		return qa.top();
	}
	int siz() {	return qa.size() - qb.size(); }
	int st()
	{
		if (siz() < 2) return 0;
		int x = tp(); pp();
		int y = tp(); ps(x);
		return y;
	}
}A,B[NN],C[NN];
void Pre()
{
	bin[0] = 1; for (int i=1;i<20;++i) bin[i] = bin[i-1] << 1;
	LOG[0] = -1; for (int i=1;i<=200000;++i) LOG[i] = LOG[i>>1] + 1;
}
void DFS(int xx,int fa)
{
	mn[0][++cnt] = deep[xx];
	pos[xx] = cnt;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].v != fa)
	{
		deep[e[i].v] = deep[xx] + 1;
		DFS(e[i].v,xx);
		mn[0][++cnt] = deep[xx];
	}
}
void GET_RT(int xx,int fa)
{
	sz[xx] = 1, f[xx] = 0;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].v != fa && !vis[e[i].v])
	{
		GET_RT(e[i].v,xx);
		sz[xx] += sz[e[i].v];
		f[xx] = max(f[xx],sz[e[i].v]);
	}
	f[xx] = max(f[xx],sum-sz[xx]);
	if (f[xx] < f[rt]) rt = xx;
}
void Div(int xx,int ff)
{
	fa[xx] = ff, vis[xx] = 1;
	for (int i=head[xx];i;i=e[i].ne)
		if (!vis[e[i].v])
		{
			sum = sz[e[i].v], rt = 0;
			GET_RT(e[i].v,xx);
			Div(rt,xx);
		}
}
int RMQ(int xx,int yy)
{
	xx = pos[xx], yy = pos[yy];
	if (yy < xx) swap(xx,yy);
	int tmp = LOG[yy-xx+1];
	return min(mn[tmp][xx],mn[tmp][yy-bin[tmp]+1]);
}
int DIS(int xx,int yy)
{
	return deep[xx] + deep[yy] - 2*RMQ(xx,yy);
}
void OFF(int xx,int yy)
{
	if (xx == yy)
	{
		B[xx].ps(0);
		if (B[xx].siz() == 2) A.ps(B[xx].tp());
	}
	if (!fa[xx]) return;
	int ff = fa[xx], D = DIS(ff,yy), tmp = C[xx].tp();
	C[xx].ps(D);
	if (D > tmp)
	{
		int mx = B[ff].tp() + B[ff].st(), szz = B[ff].siz();
		if (tmp) B[ff].er(tmp);
		B[ff].ps(D);
		int now = B[ff].tp()+B[ff].st();
		if (now > mx)
		{
			if (szz >= 2) A.er(mx);
			if (B[ff].siz() >= 2) A.ps(now);
		}
	}
	OFF(ff,yy);
}
void ON(int xx,int yy)
{
	if (xx == yy)
	{
		if (B[xx].siz() == 2) A.er(B[xx].tp());
		B[xx].er(0);
	}
	if (!fa[xx]) return;
	int ff = fa[xx], D = DIS(ff,yy), tmp = C[xx].tp();
	C[xx].er(D);
	if (D == tmp)
	{
		int mx = B[ff].tp() + B[ff].st(), szz = B[ff].siz();
		B[ff].er(D);
		if (C[xx].tp()) B[ff].ps(C[xx].tp());
		int now = B[ff].tp() + B[ff].st();
		if (now < mx)
		{
			if (szz >= 2) A.er(mx);
			if (B[ff].siz() >= 2) A.ps(now);
		}
	}
	ON(ff,yy);
}
int x,y; char ch[10];
int main()
{
	Pre();
	scanf("%d",&n);
	for (int i=1;i<n;++i) scanf("%d%d",&x,&y), Build(x,y);
	DFS(1,0);
	for (int i=1;i<=LOG[cnt];++i)
		for (int j=1;j<=cnt;++j)
			if (j+bin[i]-1 <= cnt) mn[i][j] = min(mn[i-1][j],mn[i-1][j+bin[i-1]]);
	rt = 0, sum = n, f[0] = INF;
	GET_RT(1,0);
	Div(rt,0);
	for (int i=1;i<=n;++i) C[i].ps(0);
	for (int i=1;i<=n;++i) num[i] = 1;
	for (int i=1;i<=n;++i) OFF(i,i), ++tott;
	scanf("%d",&m);
	while (m--)
	{
		scanf("%s",ch);
		if (ch[0] == 'G')
		{
			if (tott <= 1) printf("%d\n",tott-1); else printf("%d\n",A.tp());
		}
		else
		{
			scanf("%d",&x);
			if (num[x]) ON(x,x), tott --; else OFF(x,x), tott ++;
			num[x] ^= 1;
		}
	}
	return 0;
}

为什么树分治代码都辣么长(╯‵□′)╯︵┻━┻

BZOJ-2152: 聪聪可可

觉得这题比上题简单啊QAQ

询问有多少点对的距离是3的倍数。。按照模3下的数值进行统计就可以了

还是静态树分治哦QAQ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int NN = 20005;
int n,ans,sum,f[NN],sz[NN],dis[NN],tot,head[NN],rt,t[5];
bool vis[NN];

struct E
{
	int ne,v,w;
}e[NN<<1];
void Build(int xx,int yy,int zz)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy, e[tot].w = zz;
	e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx, e[tot].w = zz;
}
int GCD(int a,int b)
{
	return b==0?a:GCD(b,a%b);
}
void Get_root(int xx,int fa)
{
	f[xx] = 0, sz[xx] = 1;
	for (int i=head[xx];i;i=e[i].ne)
		if (e[i].v !=fa && !vis[e[i].v])
		{
			Get_root(e[i].v,xx);
			sz[xx] += sz[e[i].v];
			f[xx] = max(f[xx],sz[e[i].v]);
		}
	f[xx] = max(f[xx],sum-sz[xx]);
	if (f[xx] < f[rt]) rt = xx;
}

void Get_deep(int xx,int fa)
{
	t[dis[xx]]++;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].v != fa && !vis[e[i].v])
	{
		dis[e[i].v] = (dis[xx]+e[i].w)%3;
		Get_deep(e[i].v,xx);
	}
}

int Cal(int xx,int w)
{
	t[0] = t[1] = t[2] = 0,	dis[xx] = w;
	Get_deep(xx,0);
	return t[1]*t[2]*2 + t[0]*t[0];
}

void Work(int xx)
{
	ans += Cal(xx,0), vis[xx] = 1;
	for (int i=head[xx];i;i=e[i].ne)
	if (!vis[e[i].v])
	{
		ans -= Cal(e[i].v,e[i].w);
		rt = 0, sum = sz[e[i].v];
		Get_root(e[i].v,rt);
		Work(rt);
	}
}

int main()
{
	scanf("%d",&n);
	int x,y,z;
	for (int i=1;i<n;++i) scanf("%d%d%d",&x,&y,&z), Build(x,y,z%3);
	f[0] = sum = n, rt = ans = tot = 0;
	Get_root(1,0);
	Work(rt);
	int tmp = GCD(ans,n*n);
	printf("%d/%d\n",ans/tmp,n*n/tmp);
	return 0;
}

估计是代码长度最良心的题目辣

BZOJ-4317: Atm的树

按照点分治得到新树

在上面二分答案找距离<=d的点的数量

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f,NN = 30005,MM = 1200005;

int n,m,K,cnt,rt,tot=1,sum,head1[NN],head2[NN];
int a[MM],f[NN],sz[NN],pl[NN],pr[NN],ql[NN],qr[NN];
struct E
{
	int v,ne,vis,w;
}e[MM];

void Build1(int xx,int yy,int zz,int ww)
{
	e[++tot].ne = head1[xx], head1[xx] = tot, e[tot].v = yy, e[tot].vis = zz, e[tot].w = ww;
	e[++tot].ne = head1[yy], head1[yy] = tot, e[tot].v = xx, e[tot].vis = zz, e[tot].w = ww;
}
void Build2(int xx,int yy,int zz,int ww)
{
	e[++tot].ne = head2[xx], head2[xx] = tot, e[tot].v = yy, e[tot].vis = zz, e[tot].w = ww;
}
void GET_RT(int xx,int fa)
{
	sz[xx] = 1, f[xx] = 0;
	for (int i=head1[xx];i;i=e[i].ne)
	if (e[i].vis && e[i].v != fa)
	{
		GET_RT(e[i].v,xx);
		sz[xx] += sz[e[i].v];
		f[xx] = max(f[xx],sz[e[i].v]);
	}
	f[xx] = max(f[xx],sum-sz[xx]);
	if (f[xx] < f[rt]) rt = xx;
}
void DFS(int xx,int fa,int dep)
{
	a[++m] = dep;
	for (int i=head1[xx];i;i=e[i].ne)
	if (e[i].vis && e[i].v != fa) DFS(e[i].v,xx,dep+e[i].w);
}
void Build(int xx,int fa,int dep)
{
	Build2(xx,rt,cnt,dep);
	a[++m] = dep;
	for (int i=head1[xx];i;i=e[i].ne)
		if (e[i].vis && e[i].v != fa) Build(e[i].v,xx,dep+e[i].w);
} 
void Work(int xx)
{
	pl[xx] = m+1; DFS(xx,0,0); pr[xx] = m;
	sort(a+pl[xx],a+pr[xx]+1);
	for (int i=head1[xx];i;i=e[i].ne)
	if (e[i].vis)
	{
		ql[++cnt] = m + 1;
		Build(e[i].v,xx,e[i].w);
		qr[cnt] = m;
		sort(a+ql[cnt],a+qr[cnt]+1);
	}
	for (int i=head1[xx];i;i=e[i].ne)
	if (e[i].vis)
	{
		e[i].vis = e[i^1].vis = 0;
		sum = sz[e[i].v], rt = 0;
		GET_RT(e[i].v,xx);
		Work(rt);
	}
}
int Find(int xx,int yy,int zz)
{
	int l = xx, r = yy+1, mid;
	if (zz < a[xx]) return 0;
	while (l+1 < r)
	{
		mid = (l+r) >> 1;
		if (a[mid] <= zz) l = mid; else r = mid;
	}
	return l-xx+1;
}
int Check(int xx,int yy)
{
	int tmp = Find(pl[xx],pr[xx],yy);
	for (int i=head2[xx];i;i=e[i].ne)
		tmp += Find(pl[e[i].v],pr[e[i].v],yy-e[i].w) - Find(ql[e[i].vis],qr[e[i].vis],yy-e[i].w);
	return tmp;
}
int main()
{
	scanf("%d%d",&n,&K);
	++ K;
	int x,y,z;
	for (int i=1;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		Build1(x,y,1,z);
	}
	rt = 0, f[0] = INF, sum = n;
	GET_RT(1,0);
	Work(rt);
	for (int i=1;i<=n;++i)
	{
		int l = 0, r = 10*(n-1);
		while (l < r)
		{
			int mid = (l+r) >> 1;
			if (Check(i,mid) < K) l = mid+1; else r = mid;
		}
		printf("%d\n",l);
	}
	return 0;
}

BZOJ-4016: [FJOI2014]最短路径树问题

在最短路上按编号从小到大DFS，可以保证DFS出来的树就是题目要求的QAQ

在树上跑树分治$f[i][j][2]$表示前$i$棵子树，从根出发的链长为$j$下的最长长度和方案数

对于后一棵子树，记$g[i][j][2]$表示相同含义，并枚举子树上链长，更新答案

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
#define pa pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
const int NN = 30005, INF = 2000000000;
int ans1,ans2,n,K,m,tot,rt,sum;
int dis[NN],head[NN],head2[NN],fa[NN],f[NN],sz[NN],deep[NN];
bool vis[NN];
priority_queue<pa,vector<pa>,greater<pa> > que;
struct E
{
	int v,ne,w;
}e2[NN<<2],e[NN<<1];
int d[NN][2],g[NN][2];
vector <pa> v[NN];
queue <int> QUE;

void Build(int xx,int yy,int zz)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy, e[tot].w = zz;
	e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx, e[tot].w = zz;
}
void Build2(int xx,int yy,int zz)
{
	e2[++tot].ne = head2[xx], head2[xx] = tot, e2[tot].v = yy, e2[tot].w = zz;
}
void Dij()
{
	for (int i=1;i<=n;++i) dis[i] = INF;
	dis[1] = 1;
	que.push(mp(0,1));
	while (!que.empty())
	{
		int now = que.top().sec; que.pop();
		if (vis[now]) continue;
		vis[now] = 1;
		for (int i=head2[now];i;i=e2[i].ne)
		if (dis[now] + e2[i].w < dis[e2[i].v])
		{
			dis[e2[i].v] = dis[now] + e2[i].w;
			que.push(mp(dis[e2[i].v],e2[i].v));
		}
	}
}
void DFS(int xx)
{
	vis[xx] = 1;
	for (int i=head2[xx];i;i=e2[i].ne)
		if (!vis[e2[i].v] && dis[xx] + e2[i].w == dis[e2[i].v])
		{
			Build(xx,e2[i].v,e2[i].w);
			DFS(e2[i].v);
		}
}
void Get_rt(int xx)
{
	sz[xx] = 1, f[xx] = 0;
	for (int i=head[xx];i;i=e[i].ne)
	if (!vis[e[i].v] && e[i].v != fa[xx])
	{
		fa[e[i].v] = xx;
		Get_rt(e[i].v);
		f[xx] = max(f[xx],sz[e[i].v]);
		sz[xx] += sz[e[i].v];
	}
	f[xx] = max(f[xx],sum-sz[xx]);
	if (f[xx] < f[rt]) rt = xx;
}
void Work(int xx,int S)
{
	vis[xx] = 1, d[0][1] = 1;
	for (int i=head[xx];i;i=e[i].ne)
		if (!vis[e[i].v])
		{
			while (!QUE.empty()) QUE.pop();
			QUE.push(e[i].v);
			deep[e[i].v] = 1, fa[e[i].v] = xx, dis[e[i].v] = e[i].w;
			while (!QUE.empty())
			{
				int now = QUE.front(),k = deep[now]; QUE.pop();
				if (k > K) break;
				if (dis[now] > g[k][0]) g[k][0] = dis[now], g[k][1] = 0;
				if (dis[now] == g[k][0]) g[k][1] ++;
				for (int j=head[now];j;j=e[j].ne)
				if (!vis[e[j].v] && e[j].v != fa[now])
				{
					fa[e[j].v] = now, deep[e[j].v] = deep[now]+1;
					dis[e[j].v] = dis[now] + e[j].w;
					QUE.push(e[j].v);
				}
			}
			for (int j=1;j<=K;++j)
			{
				if (g[j][0] + d[K-j][0] > ans1) ans1 = g[j][0] + d[K-j][0], ans2 = 0;
				if (g[j][0] + d[K-j][0] == ans1) ans2 += g[j][1] * d[K-j][1];
			}
			for (int j=1;j<=K;++j)
			{
				if (g[j][0] > d[j][0]) d[j][0] = g[j][0], d[j][1] = 0;
				if (g[j][0] == d[j][0]) d[j][1] += g[j][1];
				g[j][0] = g[j][1] = 0;
			}
		}
	for (int i=0;i<=K;++i) d[i][0] = d[i][1] = 0;
	for (int i=head[xx];i;i=e[i].ne)
	if (!vis[e[i].v])
	{
		sum = sz[e[i].v];
		if (sz[e[i].v] > sz[xx]) sz[e[i].v] = S-sz[e[i].v];
		rt = 0;
		if (sum >= K) Get_rt(e[i].v);
		Work(rt,sz[e[i].v]);
	}
}
int main()
{
	int x,y,z;
	scanf("%d%d%d",&n,&m,&K);K--;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		v[x].pb(mp(y,z));
		v[y].pb(mp(x,z));
	}
	for (int _=1;_<=n;++_)
	{
		sort(v[_].begin(),v[_].end());
		for (int i=v[_].size()-1;i>=0;--i)
			Build2(_,v[_][i].fir,v[_][i].sec);
	}
	Dij();
	tot = 0;
	memset(vis,0,sizeof(vis));
	DFS(1);
	memset(vis,0,sizeof(vis));
	rt = 0, f[0] = INF, sum = n;
	Get_rt(1);
	Work(rt,sum);
	printf("%d %d\n",ans1,ans2);
	return 0;
}

跑最短路前的建边一个字母打错调了2小时的我感觉一点都不好

BZOJ-4372: 烁烁的游戏

每个点建一棵线段树，记录离这个点距离为d的点的权值和，然后统计求和

然而为了防止两个节点算重要给每个儿子节点多开开一棵线段树QAQ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;

const int NN = 200005,INF = 0x3f3f3f3f;
struct E
{
	int ne,v;
}e[NN<<1];
int n,m,head[NN],rt,sz[NN],mx[NN],deep[NN],fa[NN][20],tot=0,sum,f[NN];
bool vis[NN];

void Build(int xx,int yy)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
	e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx;
}
void Get_rt(int xx,int fa)
{
	sz[xx] = 1, mx[xx] = 0;
	for (int i=head[xx];i;i=e[i].ne)
		if (e[i].v != fa && !vis[e[i].v])
		{
			Get_rt(e[i].v,xx);
			sz[xx] += sz[e[i].v];
			mx[xx] = max(mx[xx],sz[e[i].v]);
		}
	mx[xx] = max(sum-sz[xx],mx[xx]);
	if (mx[xx] < mx[rt]) rt = xx;
}
void DFS2(int xx,int fa)
{
	sz[xx] = 1;
	for (int i=head[xx];i;i=e[i].ne)
		if (e[i].v != fa && !vis[e[i].v])
		{
			DFS2(e[i].v,xx);
			sz[xx] += sz[e[i].v];
		}
}
void re_Build(int xx,int fa)
{
	rt = 0;
	Get_rt(xx,0);
	int nrt = rt;
	vis[nrt] = 1, f[nrt] = fa;
	DFS2(nrt,0);
	for (int i=head[nrt];i;i=e[i].ne)
		if (!vis[e[i].v]) sum = sz[e[i].v], re_Build(e[i].v,nrt);
}
int LCA(int xx,int yy)
{
	if (deep[xx]<deep[yy]) swap(xx,yy);
	int tmp = deep[xx]-deep[yy];
	for (int i=0;i<=17;++i) if (tmp>>i&1) xx = fa[xx][i];
	for (int i=17;i>=0;--i) if (fa[xx][i]!=fa[yy][i]) xx=fa[xx][i], yy = fa[yy][i];
	return xx == yy?xx:fa[xx][0];
}
int DIS(int xx,int yy)
{
	return deep[xx] + deep[yy] - 2*deep[LCA(xx,yy)];
}
void DFS1(int xx)
{
	for (int i=1;i<=17;++i) fa[xx][i] = fa[fa[xx][i-1]][i-1];
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].v != fa[xx][0])
	{
		deep[e[i].v] = deep[xx] + 1;
		fa[e[i].v][0] = xx;
		DFS1(e[i].v);
	}
}
int tr_sz,rt1[NN],rt2[NN];
struct TR
{
	int c[2],w;
}tr[100*NN];
void Update(int &k,int L,int R,int l,int r,int v)
{
	if (!k) k = ++tr_sz, tr[k].w = 0;
	if (l<=L && r>=R) { tr[k].w += v; return; }
	int mid = (L+R) >> 1;
	if (l <= mid) Update(tr[k].c[0],L,mid,l,r,v);
	if (r > mid) Update(tr[k].c[1],mid+1,R,l,r,v);
}
int Query(int &k,int l,int r,int v)
{
	int ans = tr[k].w;
	if (!k || l == r) return tr[k].w;
	int mid = (l+r) >> 1;
	return v<=mid ? (ans + Query(tr[k].c[0],l,mid,v)) : (ans + Query(tr[k].c[1],mid+1,r,v));
}
int QQ(int xx)
{
	int ans = 0, dis;
	ans += Query(rt1[xx],0,n,0);
	for (int i=xx;f[i];i=f[i])
	{
		dis = DIS(f[i],xx);
		ans += Query(rt1[f[i]],0,n,dis) - Query(rt2[i],0,n,dis);
	}
	return ans;
}
void MM(int xx,int yy,int zz)
{
	int dis;
	Update(rt1[xx],0,n,0,yy,zz);
	for (int i=xx;f[i];i=f[i])
	{
		dis = DIS(xx,f[i]);
		if (dis > yy) continue;
		Update(rt1[f[i]],0,n,0,yy-dis,zz), Update(rt2[i],0,n,0,yy-dis,zz);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	char op;
	int x,y,z;
	for (int i=1;i<n;++i) scanf("%d%d",&x,&y), Build(x,y);
	DFS1(1);
	memset(f,0,sizeof(f));
	rt = 0, mx[rt] = INF, sum = n;
	re_Build(1,0);
	while (m--)
	{
		for (op = getchar();op!='M'&&op!='Q';op = getchar());
		if (op == 'Q') scanf("%d",&x), printf("%d\n",QQ(x));
		else scanf("%d%d%d",&x,&y,&z), MM(x,y,z);
	}
	return 0;
}

报告长官，苯宝宝大脑已被各种各样奇形怪状的树攻陷

BZOJ-1758: [Wc2010]重建计划

## Warning：此代码Time_Limit_Exceed ##

感觉像是死于 “新加数据一组”(╯‵□′)╯︵┻━┻

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
const int NN = 100010;
const double INF = 1e15,eps = 1e-4;
int f[NN],sz[NN],deep[NN],head[NN],h,t,DEP,dep,sum,rt,n,L,R,tot=0,q[NN];
bool vis[NN];
double a[NN],b[NN],d[NN],ans=0.0,mid;

struct E
{
	int ne,v,w;
}e[NN<<1];

char ch;
void read(int &x){
   while (ch = getchar(),ch < '0' || ch > '9');
   x = ch - '0';
   while (ch = getchar(),ch >= '0' && ch <= '9') x = x * 10 + ch - '0';
}
void Build(int xx,int yy,int zz)
{
	e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy, e[tot].w = zz;
	e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx, e[tot].w = zz;
}
void Get_root(int xx,int fa)
{
	sz[xx] = 1,f[xx] = 0;
	for (int i=head[xx];i;i=e[i].ne)
		if (!vis[e[i].v] && e[i].v != fa)
		{
			Get_root(e[i].v,xx);
			sz[xx] += sz[e[i].v];
			f[xx] = max(f[xx],sz[e[i].v]);
		}
	f[xx] = max(f[xx],sum-sz[xx]);
	if (f[xx] < f[rt]) rt = xx;
}
void Get_dep(int xx,int fa)
{
	sz[xx] = 1;
	deep[xx] = deep[fa] + 1;
	for (int i=head[xx];i;i=e[i].ne)
	if (!vis[e[i].v] && e[i].v != fa)
	{
		//deep[e[i].v] = deep[xx] + 1;
		Get_dep(e[i].v,xx);
		sz[xx] += sz[e[i].v];
	}
	DEP = max(DEP,deep[xx]);
}
void DFS1(int xx,int fa)
{
	if (deep[xx] > R) return;
	a[deep[xx]] = max(a[deep[xx]],d[xx]);
	for (int i=head[xx];i;i=e[i].ne)
		if (!vis[e[i].v] && e[i].v != fa)
		{
			d[e[i].v] = d[xx] + e[i].w - mid;
			DFS1(e[i].v,xx);
		}
	dep = max(dep,deep[xx]);
}
void Work(int xx)
{
	Get_root(xx,0);
	if (sz[xx] <= L) return ;
	DEP = 0;
	Get_dep(rt,0);
	double l = ans, r = 1e10, tmp, maxx;
	int mp;
	while (l < r-eps)
	{
		mid = (l+r) / 2;
		b[0] = 0;
		for (int i=1;i<=DEP;++i) b[i] = - INF;
		tmp = maxx = -INF;
		mp = 0;
		for (int i=head[rt];i;i=e[i].ne)
		if (!vis[e[i].v])
		{
			h = t = 0, a[0] = 0;
			for (int j=1;j<=DEP;++j) a[j] = -INF;
			dep = 0;
			d[e[i].v] = e[i].w - mid;
			DFS1(e[i].v,rt);
			if (mp) q[++t] = mp;
			for (int j=1;j<=dep;++j)
			{
				if (j>R) break;
				if (h<t && q[h+1] > R-j) ++h;
				if (L>=j && L-j<=DEP)
				{
					while (h<t && b[q[t]] < b[L-j]) t--;
					q[++t] = L-j;
					tmp = max(tmp,b[q[h+1]]+a[j]);
				}
				else
				if (j > L) tmp = max(tmp,b[q[h+1]]+a[j]);
			}
			for (int j=1;j<=dep;++j)
			{
				b[j] = max(b[j],a[j]);
				if (j >= L && j <= R && maxx < b[j]) maxx = b[j], mp = j;
			}
		}
		if (tmp > 0) l = mid; else r = mid;
	}
	ans = l;
	vis[rt] = 1;
	for (int i=head[rt];i;i=e[i].ne)
	if (!vis[e[i].v])
		f[rt] = sum = sz[e[i].v], Work(e[i].v);
}
int main()
{
	read(n), read(L), read(R);
//	scanf("%d%d%d",&n,&L,&R);
	int x,y,z;
	for (int i=1;i<n;++i) read(x), read(y), read(z), Build(x,y,z); //scanf("%d%d%d",&x,&y,&z), Build(x,y,z);
	sum = f[0] = n, rt = 0, deep[0] = -1;
	Work(1);
	printf("%.3lf\n",ans);
	return 0;
}