bzoj2402: 陶陶的难题II【分数规划+树链剖分+线段树维护凸包】

Description

Input

第一行包含一个正整数N，表示树中结点的个数。

第二行包含N个正实数，第i个数表示xi。

第三行包含N个正实数，第i个数表示yi 。

第四行包含N个正实数，第i个数表示pi。

第五行包含N个正实数，第i个数表示qi。

下面有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

Sample Output

2.5000

1.5000

1.5000

2.5000

HINT

100%的数据满足N,M≤ 30,000。

1<=Xi,Yi,Pi,Qi<=10^8

解题思路：

很容易往分数规划、树链剖分的方向想。

二分答案，如果有 yi+qixi+pi>ans y i + q i x i + p i > a n s ，则变形有 (yi−ans∗xi)+(qj−ans∗pj)>0 ( y i − a n s ∗ x i ) + ( q j − a n s ∗ p j ) > 0 ，所以链剖要支持找 (yi−ans∗xi)、(qj−ans∗pj) ( y i − a n s ∗ x i ) 、 ( q j − a n s ∗ p j ) 的最大值。

注意到上式都是形如 y−kx y − k x 的形式，所以最优值一定在路径上点组成的凸包与斜率为 k k 的直线的切点处，链剖时用线段树维护区间内点的凸包即可二分查找。

时间复杂度O(nlog4n)O(nlog4n)，卡卡常还是能过的。

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

const int N=,M=;
const double INF=,eps=;
struct point
{
    double x,y;
    point(){}
    point(double _x,double _y):x(_x),y(_y){}
    inline friend bool operator < (const point &a,const point &b)
    {return a.x<b.x||a.x==b.x&&a.y<b.y;}
    inline friend point operator - (const point &a,const point &b)
    {return point(a.x-b.x,a.y-b.y);}
    inline friend double operator * (const point &a,const point &b)
    {return a.x*b.y-a.y*b.x;}
};
int n,m,idx;
int id[N],pos[N],dep[N],size[N],son[N],fa[N],top[N];
int tot,first[N],nxt[N<<],to[N<<];
double a1[N],a2[N],b1[N],b2[N];
struct seg_tree
{
    int cnt,tp,st[N<<],ed[N<<];
    double X[N],Y[N];
    point p[N],a[M];
    void build(int k,int l,int r)
    {
        for(int i=l;i<=r;i++)p[i]=point(X[i],Y[i]);
        sort(p+l,p+r+);tp=;
        for(int i=l;i<=r;i++)
        {
            while(tp>&&(p[tp-]-p[i])*(p[tp]-p[i])>=)tp--;
            p[++tp]=p[i];
        }
        st[k]=cnt+;
        for(int i=;i<=tp;i++)a[++cnt]=p[i];
        ed[k]=cnt;
        if(l==r)return;
        int mid=l+r>>;
        build(k<<,l,mid),build(k<<|,mid+,r);
    }
    double get(int k,double K)
    {
        int l=st[k],r=ed[k];
        while(r-l>)
        {
            int mid=l+r>>;
            double t1=a[mid-].y-K*a[mid-].x,t2=a[mid].y-K*a[mid].x,t3=a[mid+].y-K*a[mid+].x;
            if(t1<=t2&&t2>=t3)return t2;
            else if(t1<=t2)l=mid+;
            else r=mid-;
        }
        double res=-INF;
        for(int i=l;i<=r;i++)res=max(res,a[i].y-K*a[i].x);
        return res;
    }
    double query(int k,int l,int r,int x,int y,double K)
    {
        if(l==x&&r==y)return get(k,K);
        int mid=l+r>>;
        if(y<=mid)return query(k<<,l,mid,x,y,K);
        else if(x>mid)return query(k<<|,mid+,r,x,y,K);
        else return max(query(k<<,l,mid,x,mid,K),query(k<<|,mid+,r,mid+,y,K));
    }
    double find(int x,int y,double K)
    {
        double res=-INF;
        while(top[x]!=top[y])
        {
            if(dep[top[x]]<dep[top[y]])swap(x,y);
            res=max(res,query(,,n,pos[top[x]],pos[x],K));
            x=fa[top[x]];
        }
        if(dep[x]>dep[y])swap(x,y);
        res=max(res,query(,,n,pos[x],pos[y],K));
        return res;
    }
}T1,T2;

inline void add(int x,int y)
{
    nxt[++tot]=first[x],first[x]=tot,to[tot]=y;
}

void dfs1(int u)
{
    size[u]=;
    for(int e=first[u];e;e=nxt[e])
    {
        int v=to[e];
        if(v==fa[u])continue;
        fa[v]=u,dep[v]=dep[u]+;
        dfs1(v),size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}

void dfs2(int u,int f)
{
    id[pos[u]=++idx]=u,top[u]=f;
    if(son[u])dfs2(son[u],f);
    for(int e=first[u];e;e=nxt[e])
    {
        int v=to[e];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}

int main()
{
    //freopen("lx.in","r",stdin);
    //freopen("lx.out","w",stdout);
    int x,y;
    scanf("%d",&n);
    for(int i=;i<=n;i++)scanf("%lf",&a1[i]);
    for(int i=;i<=n;i++)scanf("%lf",&a2[i]);
    for(int i=;i<=n;i++)scanf("%lf",&b1[i]);
    for(int i=;i<=n;i++)scanf("%lf",&b2[i]);
    for(int i=;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs1(),dfs2(,);
    for(int i=;i<=n;i++)
    {
        T1.X[pos[i]]=a1[i],T1.Y[pos[i]]=a2[i];
        T2.X[pos[i]]=b1[i],T2.Y[pos[i]]=b2[i];
    }
    T1.build(,,n),T2.build(,,n);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        double l=,r=;
        while(r-l>eps)
        {
            double mid=(l+r)/;
            if(T1.find(x,y,mid)+T2.find(x,y,mid)>)l=mid;
            else r=mid;
        }
        printf("%0.4lf\n",r);
    }
    return ;
}