比赛 cdcqの省选膜你赛 评测结果 WWWWWATTTTWAWWAWAAAA
题目名称 秘术「天文密葬法」 最终得分 35
用户昵称 Menci 运行时间 25.307 s
代码语言 C++ 内存使用 14.04 MiB
提交时间 2017-04-11 11:52:12
显示代码纯文本
#include <cstdio>
#include <cassert>
#include <cfloat>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>

const int MAXN = 200000;

struct Node {
	std::vector<Node *> adj;
	bool solved;
	int size, dist;

	int a, b;
	double w, sum;
} N[MAXN + 1];

int n, m;

inline void addEdge(int s, int t) {
	N[s].adj.push_back(&N[t]);
	N[t].adj.push_back(&N[s]);
}

inline int calcSize(Node *v, Node *fa = NULL) {
	v->size = 1;
	for (Node **p = &v->adj.front(), *u; p && p <= &v->adj.back() ? (u = *p) : NULL; p++) {
		if (u != fa && !u->solved) {
			v->size += calcSize(u, v);
		}
	}
	return v->size;
}

inline Node *center(Node *v, Node *fa = NULL) {
	for (Node **p = &v->adj.front(), *u; p && p <= &v->adj.back() ? (u = *p) : NULL; p++) {
		if (u != fa && !u->solved) {
			if (u->size > v->size / 2) return center(u, v);
		}
	}
	return v;
}

inline double calc(Node *root) {
	static double minOfLen[MAXN + 1], minOfLenBefore[MAXN + 1];
	if (minOfLen[0] == 0) { // Not inited
		for (int i = 0; i <= n; i++) minOfLen[i] = minOfLenBefore[i] = DBL_MAX;
	} else {
		// for (int i = 0; i <= n; i++) assert(minOfLen[i] == DBL_MAX &&  minOfLenBefore[i] == DBL_MAX);
	}
	double minHalf = DBL_MAX, minHalfBefore = DBL_MAX, min = DBL_MAX;

	static Node *all[MAXN + 1];
	int cntAll = 0;

	double res = DBL_MAX;
	for (Node **p = &root->adj.front(), *u; p && p <= &root->adj.back() ? (u = *p) : NULL; p++) {
		if (u->solved) continue;

		std::queue<Node *> q;
		q.push(u);
		u->dist = 1;
		u->sum = u->w;

		minOfLenBefore[0] = root->w;

		static Node *a[MAXN + 1];
		int cnt = 0;
		while (!q.empty()) {
			Node *v = q.front();
			q.pop();

			a[++cnt] = v;
			all[++cntAll] = v;

			if (m == -1) {
				minHalf = std::min(minHalf, v->sum);
				min = std::min(min, v->sum);
				if (minHalfBefore != DBL_MAX) min = std::min(min, minHalfBefore + v->sum);
			} else {
				if (v->dist < m) {
					minOfLen[v->dist] = std::min(minOfLen[v->dist], v->sum);
					if (minOfLenBefore[m - v->dist - 1] != DBL_MAX) {
						min = std::min(min, v->sum + minOfLenBefore[m - v->dist - 1]);
					}
				}
			}

			for (Node **p = &v->adj.front(), *u; p && p <= &v->adj.back() ? (u = *p) : NULL; p++) {
				if (!u->solved && !u->dist) {
					u->dist = v->dist + 1;
					u->sum = v->sum + u->w;
					q.push(u);
				}
			}
		}

		if (m == -1) {
			minHalfBefore = std::min(minHalfBefore, minHalf);
		} else {
			for (int i = 1; i <= cnt; i++) {
				Node *v = a[i];
				if (v->dist < m) {
					minOfLenBefore[v->dist] = std::min(minOfLenBefore[v->dist], minOfLen[v->dist]);
					minOfLen[v->dist] = DBL_MAX;
				}
			}
		}

		res = std::min(res, min);
	}

	if (m == -1) {
		res = std::min(res, root->w);
		res = std::min(res, minHalfBefore + root->w);
	} else {
		for (int i = 1; i <= cntAll; i++) {
			Node *v = all[i];
			if (v->dist < m) {
				minOfLen[v->dist] = minOfLenBefore[v->dist] = DBL_MAX;
			}
			v->dist = 0;
		}
		minOfLen[0] = minOfLenBefore[0] = DBL_MAX;
	}

	for (int i = 1; i <= cntAll; i++) N[i].dist = 0;

	return res;
}

inline double solve() {
	std::stack<Node *> s;
	s.push(&N[1]);

	double res = DBL_MAX;

	while (!s.empty()) {
		Node *v = s.top();
		s.pop();

		Node *root = center(v);
		root->solved = true;

		res = std::min(res, calc(root));

		for (Node **p = &root->adj.front(), *u; p && p <= &root->adj.back() ? (u = *p) : NULL; p++) {
			if (!u->solved) s.push(u);
		}
	}

	// printf("%lf %lf %lf %lf\n", N[1].w, N[2].w, N[3].w, res);
	return res;
}

inline bool check(double k) {
	for (int i = 1; i <= n; i++) {
		N[i].solved = false;
		N[i].w = N[i].a - k * N[i].b;
	}

	return solve() < 0;
}

int main() {
	freopen("cdcq_b.in", "r", stdin);
	freopen("cdcq_b.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) scanf("%d", &N[i].a);
	for (int i = 1; i <= n; i++) scanf("%d", &N[i].b);

	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		addEdge(u, v);
	}

	calcSize(&N[1]);

	double l = 0, r = 1e9;
	while (r - l > 1e-3) {
		double mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}

	double ans = (l + r) / 2;
	if (ans > 1e8) puts("-1");
	else printf("%.2lf\n", ans);
}