题目描述
输入
第一行包含一个正整数N，表示树中结点的个数。
第二行包含N个正实数，第i个数表示xi (1<=xi<=10^5)。第三行包含N个正实数，第i个数表示yi (1<=yi<=10^5)。第四行包含N个正实数，第i个数表示pi (1<=pi<=10^5)。第五行包含N个正实数，第i个数表示qi (1<=qi<=10^5)。下面有N-1行，每行包含两个正整数a,b(1<=a,b<=N)，表示树中的边。第N+5行包含一个正整数M，表示询问的个数。最后M行，每行包含正整数a,b(1<=a,b<=N)，表示一次询问。输出
共M行，每行一个实数，第i行的数表示第i次询问的答案。
只要你的输出和我们的输出相差不超过0.001即为正确。样例输入
5 3.0 1.0 2.0 5.0 4.0 5.0 2.0 4.0 3.0 1.0 1.0 3.0 2.0 4.0 5.0 3.0 4.0 2.0 1.0 4.0 1 2 1 3 2 4 2 5 4 2 3 4 5 2 4 3 5
样例输出
2.5000 1.5000 1.5000 2.5000
题解
分数规划+树链剖分+线段树+STL-vector+凸包二分
所求答案是分数的形式，一眼分数规划。
二分mid后问题转化为判断 $y_i+q_j-mid(x_i+p_j)$ 的最大值是否大于0。
整理得 $(y_i-mid·x_i)+(q_j-mid·p_j)$ 最大，此时可以发现 $i$ 和 $j$ 不再有关系，分开考虑最大值。
要求 $y_i-mid·x_i$ 的最大值，设其为 $b$ ，则有 $y_i=mid·x_i+b$ 中的 $b$ 最大。显然答案一定在可选区域的上凸壳上。
如果是序列上的话，可以考虑使用线段树维护区间凸包。
问题放到树上，可以使用树链剖分转化为序列问题，然后用线段树维护区间凸包。（这也是 的另一种解法）
因此先树剖转化为log段区间，然后每段区间在线段树上对应的log个节点的凸包上二分最大值，取最优解。
于是我们得到了时间复杂度为神奇的 $O(n\log^4n)$ 的做法。
由于第二（树链剖分）、三（线段树）、四（STL-vector+凸包+二分）个log很难都跑满，因此能过。
#include#include #define N 30010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1using namespace std;typedef long double ld;struct seg{ ld px[N] , py[N]; vector v[N << 2]; inline void insert(vector &v , int p) { while(v.size() > 1 && (px[v[v.size() - 1]] - px[p]) * (py[v[v.size() - 2]] - py[p]) - (py[v[v.size() - 1]] - py[p]) * (px[v[v.size() - 2]] - px[p]) < -1e-10) v.pop_back(); v.push_back(p); } void build(int l , int r , int x) { if(l == r) { v[x].push_back(l); return; } int mid = (l + r) >> 1; build(lson) , build(rson); unsigned tl = v[x << 1].size() , tr = v[x << 1 | 1].size() , pl = 0 , pr = 0; while(pl < tl || pr < tr) { if(pr == tr || (pl < tl && px[v[x << 1][pl]] < px[v[x << 1 | 1][pr]])) insert(v[x] , v[x << 1][pl ++ ]); else insert(v[x] , v[x << 1 | 1][pr ++ ]); } } ld query(int b , int e , ld k , int l , int r , int x) { if(b <= l && r <= e) { int L = 1 , R = v[x].size() - 1 , Mid , Ans = 0; while(L <= R) { Mid = (L + R) >> 1; if(py[v[x][Mid]] - k * px[v[x][Mid]] - 1e-10 > py[v[x][Mid - 1]] - k * px[v[x][Mid - 1]]) Ans = Mid , L = Mid + 1; else R = Mid - 1; } return py[v[x][Ans]] - k * px[v[x][Ans]]; } int mid = (l + r) >> 1; ld ans = -1e16; if(b <= mid) ans = max(ans , query(b , e , k , lson)); if(e > mid) ans = max(ans , query(b , e , k , rson)); return ans; }}A , B;int head[N] , to[N << 1] , next[N << 1] , cnt , fa[N] , deep[N] , si[N] , bl[N] , pos[N] , tot , n;ld vx[N] , vy[N] , vp[N] , vq[N];inline void add(int x , int y){ to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs1(int x){ int i; si[x] = 1; for(i = head[x] ; i ; i = next[i]) if(to[i] != fa[x]) fa[to[i]] = x , deep[to[i]] = deep[x] + 1 , dfs1(to[i]) , si[x] += si[to[i]];}void dfs2(int x , int c){ int i , k = 0; bl[x] = c , pos[x] = ++tot , A.px[tot] = vx[x] , A.py[tot] = vy[x] , B.px[tot] = vp[x] , B.py[tot] = vq[x]; for(i = head[x] ; i ; i = next[i]) if(to[i] != fa[x] && si[to[i]] > si[k]) k = to[i]; if(k) { dfs2(k , c); for(i = head[x] ; i ; i = next[i]) if(to[i] != fa[x] && to[i] != k) dfs2(to[i] , to[i]); }}inline ld solve(int x , int y , ld mid){ ld ans1 = -1e16 , ans2 = -1e16; while(bl[x] != bl[y]) { if(deep[bl[x]] < deep[bl[y]]) swap(x , y); ans1 = max(ans1 , A.query(pos[bl[x]] , pos[x] , mid , 1 , n , 1)); ans2 = max(ans2 , B.query(pos[bl[x]] , pos[x] , mid , 1 , n , 1)); x = fa[bl[x]]; } if(deep[x] > deep[y]) swap(x , y); ans1 = max(ans1 , A.query(pos[x] , pos[y] , mid , 1 , n , 1)); ans2 = max(ans2 , B.query(pos[x] , pos[y] , mid , 1 , n , 1)); return ans1 + ans2;}int main(){ int m , i , x , y , c; ld l , r , mid; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) scanf("%Lf" , &vx[i]); for(i = 1 ; i <= n ; i ++ ) scanf("%Lf" , &vy[i]); for(i = 1 ; i <= n ; i ++ ) scanf("%Lf" , &vp[i]); for(i = 1 ; i <= n ; i ++ ) scanf("%Lf" , &vq[i]); for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x); dfs1(1) , dfs2(1 , 1); A.build(1 , n , 1) , B.build(1 , n , 1); scanf("%d" , &m); while(m -- ) { scanf("%d%d" , &x , &y); l = 0 , r = 1e8 , c = 50; while(c -- ) { mid = (l + r) / 2; if(solve(x , y , mid) > 1e-10) l = mid; else r = mid; } printf("%.5Lf\n" , l); } return 0;}