【BZOJ 2402】陶陶的难题II

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2402

解题报告

不难发现这是一个分数规划问题
再化一化式子就可以转换成凸包上选点的问题
至于支持链上的询问我们可以套树链剖分
总的时间复杂度:$O(n \log^3 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 60009;
const double INF = 1e9;
const double EPS = 1e-4;

int n, head[N], nxt[N], to[N];
struct Point{
	double x, y;
	inline Point() {
	}
	inline Point(double a, double b):x(a), y(b) {
	}
	inline bool operator < (const Point &PP) const {
		return x < PP.x || (x == PP.x && y < PP.y);
	}
	inline bool operator == (const Point &PP) const {
		return x == PP.x && y == PP.y;
	}
 	inline Point operator - (const Point &PP) const {
		return Point(x - PP.x, y - PP.y);
	}
	inline double operator * (const Point &PP) {
		return x * PP.y - y * PP.x;
	}
	inline double slope() {
		return y / x;
	}
}d[N][2];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

class HeavyLightDecomposition{
int fa[N], sz[N], dep[N], idx[N], hvy[N], top[N];
class SegmentTree{
vector<Point> cvx[N][2];
public:
	int num[N], root, ch[N][2];
	inline void init() {
		build(root, 1, n);	
	}
	inline void update(int l, int r, double a, double *mx) {
		query(root, 1, n, l, r, a, mx);
	}
private:
	inline void query(int w, int l, int r, int L, int R, double a, double *mx) {
		if (L <= l && r <= R) {
			mx[0] = max(mx[0], cal(cvx[w][0], a));
			mx[1] = max(mx[1], cal(cvx[w][1], a));
		} else {
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				query(ch[w][0], l, mid - 1, L, R, a, mx);
			}
			if (R >= mid) {
				query(ch[w][1], mid, r, L, R, a, mx);
			}
		}
	}
	inline double cal(const vector<Point> &que, double a) {
		int l = 0, r = que.size() - 1, mid, ret = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (mid == 0 || (que[mid] - que[mid - 1]).slope() >= a) {
				ret = mid; 
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return -a * que[ret].x + que[ret].y;
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			cvx[w][0].push_back(d[num[l]][0]);
			cvx[w][1].push_back(d[num[l]][1]);
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			int ls = ch[w][0], rs = ch[w][1];
			cvx[w][0] = Merge(cvx[ls][0], cvx[rs][0]);
			cvx[w][1] = Merge(cvx[ls][1], cvx[rs][1]);
		}
	}
	inline vector<Point> Merge(const vector<Point> &c1, const vector<Point> &c2) {
		vector<Point> cur, ret;
		for (int i = 0; i < (int)c1.size(); i++) {
			cur.push_back(c1[i]);
		}
		for (int i = 0; i < (int)c2.size(); i++) {
			cur.push_back(c2[i]);
		}
		sort(cur.begin(), cur.end());
		cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
		for (int i = 0; i < (int)cur.size(); i++) {
			while ((int)ret.size() > 1) {
				int idx = ret.size() - 1;
				if ((cur[i] - ret[idx - 1]) * (ret[idx] - ret[idx - 1]) <= EPS) {
					ret.pop_back();
				} else {
					break;
				}
			}
			ret.push_back(cur[i]);
		}
		return ret;
	}
}SGT;
public:
	inline void init() {
		DFS1(1, 1);
		DFS2(1, 1);
		SGT.init();
	}	
	inline double query(int u, int v) {
		double l = 0, r = INF, ret = 0, mid;
		while (r - l > EPS) {
			mid = (l + r) * 0.5;
			if (judge(u, v, mid)) {
				ret = mid;
				l = mid;
			} else {
				r = mid;
			}
		}	
		return ret;
	}
private:
	inline bool judge(int u, int v, double a) {
		double mx[] = {-INF, -INF};
		while (top[u] != top[v]) {
			if (dep[top[u]] > dep[top[v]]) {
				SGT.update(idx[top[u]], idx[u], a, mx);
				u = fa[top[u]];
			} else {
				SGT.update(idx[top[v]], idx[v], a, mx);
				v = fa[top[v]];
			}
		}
		if (dep[u] > dep[v]) {
			SGT.update(idx[v], idx[u], a, mx);
		} else {
			SGT.update(idx[u], idx[v], a, mx);
		}
		return mx[0] + mx[1] > 0;
	}
	inline void DFS1(int w, int f) {
		fa[w] = f;
		sz[w] = 1;
		dep[w] = dep[f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != f) {
				DFS1(to[i], w);
				sz[w] += sz[to[i]];
				if (sz[to[i]] > sz[hvy[w]]) {
					hvy[w] = to[i];
				}
			}
		}
	}
	inline void DFS2(int w, int t) {
		static int dcnt = 0;
		SGT.num[idx[w] = ++dcnt] = w;
		top[w] = t;
		if (hvy[w]) {
			DFS2(hvy[w], t);
		}
		for (int i = head[w]; i; i = nxt[i]) {
			if (to[i] != fa[w] && to[i] != hvy[w]) {
				DFS2(to[i], to[i]);
			}
		}
	}
}HLD;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][0].y);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].x);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lf", &d[i][1].y);
	}
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	HLD.init();
	for (int i = read(); i; i--) {
		printf("%.10lf\n", HLD.query(read(), read()));
	}
	return 0;
}