陶陶的难题II
时间限制：40s 空间限制：128MB
题目描述
输入格式
第一行包含一个正整数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
提示
100%的数据满足N,M≤ 30,000。
1<=Xi,Yi,Pi,Qi<=10^8
题目来源
没有写明来源
首先根据答案是个分数以及“你的输出和我们的输出相差不超过0.001即为正确”可以想到分数规划。然后化下式子可以发现i和j是可以分开考虑的，加上题目求的式子是一个分数可以自然想到凸包。但是我们怎么维护这个凸包呢？由于没有修改，我们可以通过线段树套std::vector维护，合并时由于两边横坐标都是单增的所以用类似归并排序的方法即可。最后，一般凸包问题都是用三分，但是仔细思考会发现其实二分也可以做。这样总的复杂度就是四个log的（分数规划，树链剖分，线段树，二分查找各一个）。由于复杂度并不满所以可以跑过（当然能用$O(n \log^4 n)$卡掉$O(n^2)$的题并不多见）
#include<cstdio>
#include<vector>
#include<algorithm>
#define ls (x<<1)
#define rs ((x<<1)|1)
#define lson ls,L,mid
#define rson rs,mid+1,R
#define rep(i,l,r) for (int i=l; i<=r; i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
typedef long double ld;
using namespace std; const int N=;
int n,m,u,v,cnt,nd,dfn[N],d[N],top[N],sz[N],son[N],f[N],h[N],to[N<<],nxt[N<<];
ld vx[N],vy[N],vp[N],vq[N]; void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } struct Seg{
ld px[N],py[N];
vector<int>V[N<<]; void insert(vector<int>&V,int p){
while (V.size()> && (px[V[V.size()-]]-px[p])*(py[V[V.size()-]]-py[p])-(py[V[V.size()-]]-py[p])*(px[V[V.size()-]]-px[p])<-1e-) V.pop_back();
V.push_back(p);
} void build(int x,int L,int R){
if (L==R){ V[x].push_back(L); return; }
int mid=(L+R)>>;
build(lson); build(rson);
int pl=,pr=,tl=V[ls].size(),tr=V[rs].size();
while (pl<tl || pr<tr)
if (pr==tr || (pl<tl && px[V[ls][pl]]<px[V[rs][pr]])) insert(V[x],V[ls][pl++]);
else insert(V[x],V[rs][pr++]);
} ld que(int x,int L,int R,int l,int r,ld k){
if (L==l && R==r){
int ll=,rr=V[x].size()-,mid,ans=;
while (ll<=rr){
mid=(ll+rr)>>;
if (py[V[x][mid]]-k*px[V[x][mid]]-1e->py[V[x][mid-]]-k*px[V[x][mid-]]) ans=mid,ll=mid+; else rr=mid-;
}
return py[V[x][ans]]-k*px[V[x][ans]];
}
int mid=(L+R)>>;
if (r<=mid) return que(lson,l,r,k);
else if (l>mid) return que(rson,l,r,k);
else return max(que(lson,l,mid,k),que(rson,mid+,r,k));
}
}A,B; ld solve(int x,int y,ld ans){
ld res1=-1e16,res2=-1e16;
while (top[x]!=top[y]){
if (d[top[x]]<d[top[y]]) swap(x,y);
res1=max(res1,A.que(,,n,dfn[top[x]],dfn[x],ans));
res2=max(res2,B.que(,,n,dfn[top[x]],dfn[x],ans));
x=f[top[x]];
}
if (d[x]>d[y]) swap(x,y);
res1=max(res1,A.que(,,n,dfn[x],dfn[y],ans));
res2=max(res2,B.que(,,n,dfn[x],dfn[y],ans));
return res1+res2;
} void dfs(int x,int fa){
sz[x]=; son[x]=;
For(i,x) if ((k=to[i])!=fa){
f[k]=x; d[k]=d[x]+; dfs(k,x); sz[x]+=sz[k];
if (sz[k]>sz[son[x]]) son[x]=k;
}
} void dfs1(int x,int tp){
dfn[x]=++nd; top[x]=tp; A.px[nd]=vx[x]; A.py[nd]=vy[x]; B.px[nd]=vp[x]; B.py[nd]=vq[x];
if (son[x]) dfs1(son[x],tp);
For(i,x) if ((k=to[i])!=f[x] && k!=son[x]) dfs1(k,k);
} int main(){
freopen("bzoj2402.in","r",stdin);
freopen("bzoj2402.out","w",stdout);
scanf("%d",&n);
rep(i,,n) scanf("%Lf",&vx[i]);
rep(i,,n) scanf("%Lf",&vy[i]);
rep(i,,n) scanf("%Lf",&vp[i]);
rep(i,,n) scanf("%Lf",&vq[i]);
rep(i,,n-) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(,); dfs1(,);
A.build(,,n); B.build(,,n);
for (scanf("%d",&m); m--; ){
scanf("%d%d",&u,&v);
ld L=,R=1e8; int c=;
while (c--){
ld mid=(L+R)/;
if (solve(u,v,mid)>1e-) L=mid; else R=mid;
}
printf("%.5Lf\n",L);
}
return ;
}