比赛 |
cdcqの省选膜你赛 |
评测结果 |
AAAAAAWWWAWAWWAWAAAA |
题目名称 |
秘术「天文密葬法」 |
最终得分 |
65 |
用户昵称 |
__stdcall |
运行时间 |
7.086 s |
代码语言 |
C++ |
内存使用 |
11.96 MiB |
提交时间 |
2017-04-11 22:11:14 |
显示代码纯文本
#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);
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] = 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_clear( int u, int fa, int d ) {
using namespace Tree;
f2[d] = INFD;
for( int e = head[u]; ~e; e = nxt[e] ) {
int v = to[e];
if( del[v] || v == fa ) continue;
dfs_clear(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 ) scs = true;
return;
}
if( totw + f[m-d-1] < EPS ) 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 ) {
using namespace Tree;
f[d] = min(f[d], f2[d]);
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);
}
}
void divide( int u ) {
using namespace Tree;
u = FindG::findg(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_clear(v, u, 1);
dfs(v, u, 1, w[u]);
dfs_assign(v, u, 1);
}
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 )
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();
else Solve2::solve();
return 0;
}