记录编号	393889	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	秘术「天文密葬法」	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	6.274 s
提交时间	2017-04-12 12:36:38	内存使用	11.96 MiB

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long ll;
const double INFD = 1e100;
const int MAXN = 200010;

int n, m, a[MAXN], b[MAXN];

namespace Tree {
	int head[MAXN], nxt[MAXN<<1], to[MAXN<<1], eidx = 0;
	void init() {
		memset(head, -1, sizeof(head));
	}
	void adde( int u, int v ) {
		to[eidx] = v, nxt[eidx] = head[u], head[u] = eidx++;
		to[eidx] = u, nxt[eidx] = head[v], head[v] = eidx++;
	}
}

namespace Solve {
	void input() {
		scanf( "%d%d", &n, &m );
		for( int i = 1; i <= n; ++i ) scanf( "%d", a+i );
		for( int i = 1; i <= n; ++i ) scanf( "%d", b+i );
		for( int i = 0; i < n-1; ++i ) {
			int u, v; scanf( "%d%d", &u, &v );
			Tree::adde(u,v);
		}
	}

	int dis[MAXN];
	queue<int> q;
	bool check() {
		using namespace Tree;
		memset( dis, 0x3f, sizeof(dis) );
		q.push(1), dis[1] = 1;
		while( !q.empty() ) {
			int u = q.front(); q.pop();
			for( int e = head[u]; ~e; e = nxt[e] ) {
				int v = to[e];
				if( dis[u] + 1 < dis[v] ) {
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
		int s = max_element(dis+1, dis+n+1) - dis;
		memset( dis, 0x3f, sizeof(dis) );
		q.push(s), dis[s] = 1;
		while( !q.empty() ) {
			int u = q.front(); q.pop();
			for( int e = head[u]; ~e; e = nxt[e] ) {
				int v = to[e];
				if( dis[u] + 1 < dis[v] ) {
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
		return *max_element(dis+1, dis+n+1) >= m;
	}
}

namespace Solvem1 {
	void solve() {
		double ans = (double)a[1] / b[1];
		for( int i = 2; i <= n; ++i )
			ans = min(ans, (double)a[i] / b[i]);
		printf( "%.2lf\n", ans );
	}
}

namespace Solve1 {
	const int MAXN = 1005;
	int dis[MAXN];
	ll tota[MAXN], totb[MAXN];
	queue<int> q;
	void solve() {
		using namespace Tree;
		double ans = INFD;
		for( int s = 1; s <= n; ++s ) {
			memset( dis, 0x3f, sizeof(dis) );
			dis[s] = 1, tota[s] = a[s], totb[s] = b[s], q.push(s);
			while( !q.empty() ) {
				int u = q.front(); q.pop();
				if( dis[u] == m ) {
					ans = min(ans, (double)tota[u] / totb[u]);
					continue;
				}
				for( int e = head[u]; ~e; e = nxt[e] ) {
					int v = to[e];
					if( dis[u] + 1 < dis[v] ) {
						dis[v] = dis[u] + 1;
						tota[v] = tota[u] + a[v];
						totb[v] = totb[u] + b[v];
						q.push(v);
					}
				}
			}
		}
		printf( "%.2lf\n", ans );
	}
}

namespace Solve2 {
	bool del[MAXN];
}

namespace FindG {
	int sz[MAXN], totsz;
	int g, maxv;
	int dfs_sz( int u, int fa ) {
		using namespace Tree;
		using Solve2::del;
		sz[u] = 1;
		for( int e = head[u]; ~e; e = nxt[e] ) {
			int v = to[e];
			if( del[v] || v == fa ) continue;
			sz[u] += dfs_sz(v,u);
		}
		return sz[u];
	}
	void dfs_dp( int u, int fa ) {
		using namespace Tree;
		using Solve2::del;
		int f = totsz - sz[u];
		for( int e = head[u]; ~e; e = nxt[e] ) {
			int v = to[e];
			if( del[v] || v == fa ) continue;
			dfs_dp(v,u);
			f = max(f, sz[v]);
		}
		if( f < maxv ) maxv = f, g = u;
	}
	int findg( int u ) {
		totsz = dfs_sz(u,0);
		// printf( "totsz = %d, ", totsz );
		g = u, maxv = totsz;
		dfs_dp(u,0);
		return g;
	}
}

namespace Solve2 {
	const double EPS = 1e-6;
	double w[MAXN], f[MAXN], f2[MAXN];
	bool scs;

	void dfs_clear_f( int u, int fa, int d ) {
		using namespace Tree;
		f[d] = f2[d] = f[m-d-1] = f2[m-d-1] = INFD;
		for( int e = head[u]; ~e; e = nxt[e] ) {
			int v = to[e];
			if( del[v] || v == fa ) continue;
			dfs_clear_f(v, u, d+1);
		}
	}
	void dfs( int u, int fa, int d, double totw ) {
		using namespace Tree;
		totw += w[u];
		f2[d] = min(f2[d], totw);
		if( d == m-1 ) {
			if( totw < EPS ) {
				// printf( "totw = %.2lf < EPS\n", totw );
				scs = true;
			}
			return;
		}
		if( totw + f[m-d-1] < EPS ) {
			// printf( "u = %d, totw = %lf + f[%d-%d-1] = %lf < EPS\n", u, totw, m, d, f[m-d-1] );
			scs = true;
		}
		for( int e = head[u]; ~e; e = nxt[e] ) {
			int v = to[e];
			if( del[v] || v == fa ) continue;
			dfs(v, u, d+1, totw);
		}
	}
	void dfs_assign( int u, int fa, int d, double wr ) {
		using namespace Tree;
		f[d] = min(f[d], f2[d]-wr);
		for( int e = head[u]; ~e; e = nxt[e] ) {
			int v = to[e];
			if( del[v] || v == fa ) continue;
			dfs_assign(v, u, d+1, wr);
		}
	}
	void divide( int u ) {
		using namespace Tree;
		// printf( "divide(%d), ", u );
		u = FindG::findg(u);
		// printf( "root = %d\n", u );
		del[u] = true;
		dfs_clear_f(u,0,0);
		for( int e = head[u]; ~e; e = nxt[e] ) {
			int v = to[e];
			if( del[v] ) continue;
			dfs(v, u, 1, w[u]);
			dfs_assign(v, u, 1, w[u]);
		}
		for( int e = head[u]; ~e; e = nxt[e] ) {
			int v = to[e];
			if( del[v] ) continue;
			divide(v);
		}
	}
	bool check( double k ) {
		for( int i = 1; i <= n; ++i ) {
			// printf( "a[%d] = %d, b[%d] = %d, w[%d] = %.2lf\n", i, a[i], i, b[i], i, w[i] );
			w[i] = a[i] - b[i]*k;
		}
	    scs = false;
		memset( del, false, sizeof(del) );
		divide(1);
		return scs;
	}
	
	void solve() {
		double low = 0, high = 200000;
		while( high-low > EPS ) {
			double mid = (low + high)/2;
			if( check(mid) ) high = mid;
			else low = mid;
		}
		printf( "%.2lf\n", low );
	}
}

int main() {
	freopen( "cdcq_b.in", "r", stdin );
	freopen( "cdcq_b.out", "w", stdout );
	Tree::init();
	Solve::input();
	if( m == -1 || m == 1 ) {
		Solvem1::solve();
		return 0;
	}
	if( !Solve::check() ) {
		puts("-1");
		return 0;
	}
	if( n <= 1000 ) Solve1::solve(); // Brute Force
	else Solve2::solve();
	return 0;
}