相关链接
题目传送门: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; }