2402: 陶陶的难题II
Time Limit: 40 Sec Memory Limit: 128 MBSec Special JudgeSubmit: 68 Solved: 45
[Submit][Status]
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
注意题目中有这么一句话：“只要你的输出和我们的输出相差不超过0.001即为正确。”，这句话可以算作是二分答案的标志，由于1.4999...和1.5000...无论如何精确，四舍五入后都不同，所以这样的二分题只会用spj，反过来，也能证明这道题一定要用二分。
设原式x==p1
y==v1
p==p2
q==v2
二分答案ans
(v1+v2)/(p1+p2)>=ans
(v1+v2)>=ans*p1+ans*p2
(v1-ans*p1) + (v2-ans*p2)>=0
对于二分的ans我们只需要分别处理前半部分和后半部分的最大值即可。
v1-ans*p1==c
-p1*ans+v1==c
原式 -x*ans+y==c
可看做对于区间内每一个(x,y)，存在一条斜率k=-x,截距b=y的直线，套斜率优化的方法，预处理维护凸包链剖线段树维护即可。
时间复杂度O(Qlog^3(n))，常数较小
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define MAXN 31000 #define MAXV MAXN #define MAXE MAXV*2 #define MAXT MAXN*4 #define lch (now<<1) #define rch (now<<1^1) #define smid ((sgt[now].l+sgt[now].r)>>1) #define maxval 1e8 #define eps 1e-5 #define inf 1e100 typedef double real; int n; real v1[MAXN],v2[MAXN],v3[MAXN],v4[MAXN]; int dfsq[MAXN]; struct sgt_node { int l,r,lev; int tot0,tot1; }sgt[MAXT]; struct line { real k,b; line(real k,real b):k(k),b(b){} line(){}; real get_h(real x) { return k*x+b; } void print() { printf("Line: k=%.2lf b=%.2lf ",k,b); } }sgc[2][20][MAXN]; struct point { real x,y; point(real x,real y):x(x),y(y){}; point(){} void print() { printf("Point: (%.2lf,%.2lf) ",x,y); } }sgp[2][20][MAXN]; bool cmp_point_x(const point &p1,const point &p2) { return p1.x<p2.x; } point crossover(line l1,line l2) { point res; res.x=(l1.b-l2.b)/(l2.k-l1.k); res.y=res.x*l1.k+l1.b; return res; } pair<real,real> sgt_getv(int now,real ps) { pair<real,real> res; int x; x=lower_bound(&sgp[0][sgt[now].lev][sgt[now].l+1],&sgp[0][sgt[now].lev][sgt[now].l+sgt[now].tot0],point(ps,-inf),cmp_point_x) -sgp[0][sgt[now].lev]-1; res.first=sgc[0][sgt[now].lev][x].get_h(ps); x=lower_bound(&sgp[1][sgt[now].lev][sgt[now].l+1],&sgp[1][sgt[now].lev][sgt[now].l+sgt[now].tot1],point(ps,-inf),cmp_point_x) -sgp[1][sgt[now].lev]-1; res.second=sgc[1][sgt[now].lev][x].get_h(ps); return res; } void Combine(line* res,point* pres,int& totr,line* h1,const int& tot1,line *h2,const int& tot2) { int t1,t2; line lnow; t1=t2=0; while (t1!=tot1 || t2!=tot2) { if (t1<tot1 && t2<tot2) { if (h1[t1].k<h2[t2].k) { lnow=h1[t1++]; }else { lnow=h2[t2++]; } }else if (t1==tot1) { lnow=h2[t2++]; }else if (t2==tot2) { lnow=h1[t1++]; } if (totr<=1) { res[totr]=lnow; if (totr) pres[totr]=crossover(res[totr-1],res[totr]); totr++; }else { while (totr>1 && crossover(res[totr-2],lnow).y>=pres[totr-1].y)totr--; res[totr]=lnow; pres[totr]=crossover(res[totr-1],res[totr]); totr++; } } } void Build_sgt(int now,int l,int r,int lev) { sgt[now].l=l,sgt[now].r=r; sgt[now].lev=lev; if (l==r) { sgc[0][lev][l]=line(-v2[dfsq[l]],v1[dfsq[l]]); sgc[1][lev][l]=line(-v4[dfsq[l]],v3[dfsq[l]]); sgt[now].tot0=sgt[now].tot1=1; // printf("At position%d: ",l); // printf("L1:");sgc[0][lev][l].print(); //printf("L2:");sgc[1][lev][l].print(); return ; } Build_sgt(lch,l,smid,lev+1); Build_sgt(rch,smid+1,r,lev+1); Combine(&sgc[0][lev][l],&sgp[0][lev][l],sgt[now].tot0,&sgc[0][lev+1][l],sgt[lch].tot0,&sgc[0][lev+1][smid+1],sgt[rch].tot0); Combine(&sgc[1][lev][l],&sgp[1][lev][l],sgt[now].tot1,&sgc[1][lev+1][l],sgt[lch].tot1,&sgc[1][lev+1][smid+1],sgt[rch].tot1); /* printf("At position[%d,%d]: ",l,r); for (int i=l;i<l+sgt[now].tot0;i++) { sgc[0][lev][i].print(); if (i!=l) sgp[0][lev][i].print(); }*/ } void Query_sgt(int now,int l,int r,vector<int>& res) { if (sgt[now].l==l && sgt[now].r==r) { res.push_back(now); return ; } if (r<=smid) { Query_sgt(lch,l,r,res); }else if(smid<l) { Query_sgt(rch,l,r,res); }else { Query_sgt(lch,l,smid,res); Query_sgt(rch,smid+1,r,res); } } struct Edge { int np,val; Edge *next; }E[MAXE],*V[MAXV]; int tope=-1; void addedge(int x,int y) { E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope]; } int siz[MAXN],depth[MAXN]; int pnt[MAXN]; int top[MAXN],son[MAXN]; void dfs1(int now) { Edge *ne; int mxsiz=0; siz[now]=1; for (ne=V[now];ne;ne=ne->next) { if (ne->np==pnt[now])continue; pnt[ne->np]=now; depth[ne->np]=depth[now]+1; dfs1(ne->np); siz[now]+=siz[ne->np]; if (siz[ne->np]>mxsiz) { mxsiz=siz[ne->np]; son[now]=ne->np; } } } int pos[MAXN],dfstime; void dfs2(int now) { Edge *ne; pos[now]=++dfstime; dfsq[dfstime]=now; if (son[now]) { top[son[now]]=top[now]; dfs2(son[now]); } for (ne=V[now];ne;ne=ne->next) { if (ne->np==pnt[now] || ne->np==son[now])continue; top[ne->np]=ne->np; dfs2(ne->np); } } real search_m(int x,int y) { vector<pair<real,real> > vec1,vec2; while (x!=y) { if (depth[x]>=depth[y]) { vec1.push_back(make_pair(v1[x],v2[x])); vec2.push_back(make_pair(v3[x],v4[x])); x=pnt[x]; }else { vec1.push_back(make_pair(v1[y],v2[y])); vec2.push_back(make_pair(v3[y],v4[y])); y=pnt[y]; } } vec1.push_back(make_pair(v1[x],v2[x])); vec2.push_back(make_pair(v3[x],v4[x])); real mxv=0; for (int i=0;i<vec1.size();i++) for (int j=0;j<vec2.size();j++) mxv=max(mxv,(vec1[i].first+vec2[j].first)/(vec1[i].second+vec2[j].second)); return mxv; } int main() { freopen("input.txt","r",stdin); //设原式x==p1 //y==v1 //p==p2 //q==v2 //(v1+v2)/(p1+p2)>=ans //(v1+v2)>=ans*p1+ans*p2 //(v1-ans*p1) + (v2-ans*p2)>=0 //对于二分的ans我们只需要分别处理前半部分和后半部分的最大值即可。 //v1-ans*p1==c //-p1*ans+v1==c //原式 -x*ans+y==c scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lf",v2+i);//分母1 for (int i=1;i<=n;i++) scanf("%lf",v1+i);//分子1 for (int i=1;i<=n;i++) scanf("%lf",v4+i);//分母2 for (int i=1;i<=n;i++) scanf("%lf",v3+i);//分子2 int x,y; for (int i=1;i<n;i++) { scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dfs1(1); top[1]=1; dfs2(1); Build_sgt(1,1,n,0); int q; real ans=0; scanf("%d",&q); vector<int> vec; for (int i=0;i<q;i++) { scanf("%d%d",&x,&y); vec.clear(); while (true) { if (top[x]==top[y]) { if (pos[x]>pos[y])swap(x,y); Query_sgt(1,pos[x],pos[y],vec); break; } if (depth[top[x]]<depth[top[y]])swap(x,y); Query_sgt(1,pos[top[x]],pos[x],vec); x=pnt[top[x]]; } real l=0,r=maxval; real mid; real mx1,mx2; while (r-l>eps) { mid=(l+r)/2; mx1=mx2=-inf; pair<real,real> pr; for (int j=0;j<vec.size();j++) { pr=sgt_getv(vec[j],mid); mx1=max(mx1,pr.first); mx2=max(mx2,pr.second); } if (mx1+mx2>=0) l=mid; else r=mid; } printf("%.5lf ",l+eps); } }