【BZOJ2402】陶陶的难题II 分数规划+树链剖分+线段树+凸包 【BZOJ2402】陶陶的难题II
Description
Input
第一行包含一个正整数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)，表示一次询问。
Output
共M行，每行一个实数，第i行的数表示第i次询问的答案。
只要你的输出和我们的输出相差不超过0.001即为正确。
Sample Input
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
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
Sample Output
2.5000
1.5000
1.5000
2.5000
1.5000
1.5000
2.5000
HINT
100%的数据满足N,M≤ 30,000。
1<=Xi,Yi,Pi,Qi<=10^8
题解：想到了分数规划、凸包，没想到线段树，md这题没有修改操作啊！
先二分答案mid，那么我们想要找到路径上是否有两个点的$yi+qj-mid*(xi+pj)>0$，那么显然我们要找的就是$yi-mid*xi$和$qj-mid*pj$的最大值，可以分开处理。
发现yi-mid*xi的最大值可以用凸包来搞。我们用树剖+线段树，线段树的每个节点处都维护了它的区间中所有点形成的上凸包。我们在查询时先找到线段树上的对应区间，然后在凸包上二分即可。
总复杂度：二分、树剖、线段树、树上二分，各一个log，所以是$O(nlog_n^4)$的，居然能过（其中的有些log常数比较小）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long double ld;
const int maxn=30010;
const ld eps=1e-10;
int n,m,tot,cnt;
int head[maxn],to[maxn<<1],next[maxn<<1],dep[maxn],siz[maxn],fa[maxn],top[maxn],p[maxn],q[maxn],rt[maxn],son[maxn];
struct node
{
double x,y;
node() {}
node(double a,double b) {x=a,y=b;}
node operator - (const node &a) const {return node(x-a.x,y-a.y);}
ld operator * (const node &a) const {return (ld)x*a.y-(ld)y*a.x;}
};
bool cmpx(const node &a,const node &b)
{
return a.x<b.x;
}
struct sag
{
node v[maxn];
vector<node> s[maxn<<2];
int top[maxn<<2];
void build(int l,int r,int x)
{
int i;
for(i=l;i<=r;i++) s[x].push_back(v[q[i]]);
sort(s[x].begin(),s[x].end(),cmpx);
for(top[x]=0,i=0;i<(int)s[x].size();i++)
{
while(top[x]>1&&(s[x][top[x]-1]-s[x][top[x]-2])*(s[x][i]-s[x][top[x]-1])>-eps) top[x]--;
s[x][top[x]++]=s[x][i];
}
if(l==r) return ;
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
}
double query(int l,int r,int x,int a,int b,double k)
{
int mid;
if(a<=l&&r<=b)
{
l=0,r=top[x]-1;
while(l<r)
{
mid=(l+r)>>1;
if(ld(s[x][mid+1].y-s[x][mid].y)<ld(s[x][mid+1].x-s[x][mid].x)*k+eps) r=mid;
else l=mid+1;
}
return s[x][r].y-s[x][r].x*k;
}
mid=(l+r)>>1;
if(b<=mid) return query(l,mid,lson,a,b,k);
if(a>mid) return query(mid+1,r,rson,a,b,k);
return max(query(l,mid,lson,a,b,k),query(mid+1,r,rson,a,b,k));
}
}s1,s2;
void dfs1(int x)
{
siz[x]=1;
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa[x])
{
fa[to[i]]=x,dep[to[i]]=dep[x]+1,dfs1(to[i]),siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
}
}
void dfs2(int x,int tp)
{
top[x]=tp,p[x]=++p[0],q[p[0]]=x;
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
inline double ask(int x,int y,double k)
{
double a1=-1e16,a2=-1e16;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
a1=max(a1,s1.query(1,n,1,p[top[x]],p[x],k));
a2=max(a2,s2.query(1,n,1,p[top[x]],p[x],k));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
a1=max(a1,s1.query(1,n,1,p[x],p[y],k));
a2=max(a2,s2.query(1,n,1,p[x],p[y],k));
return a1+a2;
}
inline void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
//freopen("bz2402.in","r",stdin);
n=rd();
int i,a,b;
for(i=1;i<=n;i++) scanf("%lf",&s1.v[i].x);
for(i=1;i<=n;i++) scanf("%lf",&s1.v[i].y);
for(i=1;i<=n;i++) scanf("%lf",&s2.v[i].x);
for(i=1;i<=n;i++) scanf("%lf",&s2.v[i].y);
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),add(a,b),add(b,a);
dep[1]=1,dfs1(1),dfs2(1,1);
s1.build(1,n,1),s2.build(1,n,1);
m=rd();
for(i=1;i<=m;i++)
{
a=rd(),b=rd();
double l=0,r=1e8,mid;
while(r-l>1e-5)
{
mid=(l+r)/2;
if(ask(a,b,mid)>=0) l=mid;
else r=mid;
}
printf("%.5lf
",l);
}
return 0;
}//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