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
解题思路：
那个式子非常像0/1分数规划。
发现pq式子和xy的式子结构相同，所以用同一种方法维护。
二分答案，看表达式的值。
为了寻找最大值可以将x与y移至方程两侧，发现就是一个直线方程寻找最大截距。
凸包没跑了。
将树链上的点维护成凸包二分答案取值。
开两颗线段树存。
代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll spc<<1
#define rrr spc<<1|1
typedef long long lnt;
const double eps=1e-;
const int N=;
struct trnt{
int l,r;
};
struct data{
double x,y;
bool friend operator < (data a,data b)
{
return a.x<b.x;
}
}tmp[N];
struct pnt{
int hd;
int fa;
int dp;
int tp;
int wgt;
int ind;
int mxs;
double x,y,p,q;
}p[N];
struct ent{
int twd;
int lst;
}e[N<<];
class segment_tree{
public:
void Build(int l,int r,int spc)
{
int bot=tr[spc].l=top+;
for(int i=l;i<=r;i++)
val[++top]=ln[i];
std::sort(val+tr[spc].l,val+top+);
int cel=top;
top=bot;
for(int i=bot+;i<=cel;i++)
{
while(top>bot&&(val[top].y-val[top-].y)*(val[i].x-val[top].x)<(val[i].y-val[top].y)*(val[top].x-val[top-].x)-eps)
top--;
val[++top]=val[i];
}
tr[spc].r=top;
if(l==r)
return ;
int mid=(l+r)>>;
Build(l,mid,lll);
Build(mid+,r,rrr);
return ;
}
double query(int l,int r,int ll,int rr,int spc,double k)
{
if(l>rr||ll>r)
return -1e9;
if(ll<=l&&r<=rr)
{
double ans;
int L=tr[spc].l;
int R=tr[spc].r;
while(L<R)
{
int mid=(L+R)>>;
if(val[mid+].y-val[mid].y<(val[mid+].x-val[mid].x)*k+eps)
{
R=mid;
}else
L=mid+;
}
ans=val[R].y-val[R].x*k;
return ans;
}
int mid=(l+r)>>;
return std::max(query(l,mid,ll,rr,lll,k),query(mid+,r,ll,rr,rrr,k));
}
void Insert(int l,int r,data *a)
{
for(int i=l;i<=r;i++)
ln[i]=a[i];
return ;
}
private:
trnt tr[N];
data ln[N];
data val[N];
int top;
}S[];
int n,m;
int cnt;
int dfn;
void ade(int f,int t)
{
cnt++;
e[cnt].twd=t;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void Basic_dfs(int x,int f)
{
p[x].fa=f;
p[x].dp=p[f].dp+;
p[x].wgt=;
int maxs=-;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f)
continue;
Basic_dfs(to,x);
p[x].wgt+=p[to].wgt;
if(maxs<p[to].wgt)
{
maxs=p[to].wgt;
p[x].mxs=to;
}
}
return ;
}
void Build_dfs(int x,int top)
{
if(!x)
return ;
p[x].ind=++dfn;
p[x].tp=top;
Build_dfs(p[x].mxs,top);
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].ind)
continue;
Build_dfs(to,to);
}
return ;
}
int Lca(int x,int y)
{
while(p[x].tp!=p[y].tp)
{
if(p[p[x].tp].dp<p[p[y].tp].dp)
std::swap(x,y);
x=p[p[x].tp].fa;
}
if(p[x].dp>p[y].dp)
std::swap(x,y);
return x;
}
bool check(int x,int y,double lambda)
{
double a=-1e9,b=-1e9;
int z=Lca(x,y);
while(p[x].tp!=p[z].tp)
{
a=std::max(S[].query(,n,p[p[x].tp].ind,p[x].ind,,lambda),a);
b=std::max(S[].query(,n,p[p[x].tp].ind,p[x].ind,,lambda),b);
x=p[p[x].tp].fa;
}
a=std::max(S[].query(,n,p[z].ind,p[x].ind,,lambda),a);
b=std::max(S[].query(,n,p[z].ind,p[x].ind,,lambda),b);
while(p[y].tp!=p[z].tp)
{
a=std::max(S[].query(,n,p[p[y].tp].ind,p[y].ind,,lambda),a);
b=std::max(S[].query(,n,p[p[y].tp].ind,p[y].ind,,lambda),b);
y=p[p[y].tp].fa;
}
a=std::max(S[].query(,n,p[z].ind,p[y].ind,,lambda),a);
b=std::max(S[].query(,n,p[z].ind,p[y].ind,,lambda),b);
return a+b>eps;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf",&p[i].x);
for(int i=;i<=n;i++)
scanf("%lf",&p[i].y);
for(int i=;i<=n;i++)
scanf("%lf",&p[i].p);
for(int i=;i<=n;i++)
scanf("%lf",&p[i].q);
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
ade(a,b);
ade(b,a);
}
Basic_dfs(,);
Build_dfs(,);
for(int i=;i<=n;i++)
tmp[p[i].ind]=(data){p[i].x,p[i].y};
S[].Insert(,n,tmp);
for(int i=;i<=n;i++)
tmp[p[i].ind]=(data){p[i].p,p[i].q};
S[].Insert(,n,tmp);
S[].Build(,n,);
S[].Build(,n,);
scanf("%d",&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
double l=,r=1e8;
while(fabs(l-r)>=1e-)
{
double mid=(l+r)/2.00;
if(check(a,b,mid))
l=mid;
else
r=mid;
}
printf("%.4lf\n",l);
}
return ;
}