orz mhy。看mhy的刷题记录成为了我成天的刷题方向了。
其实最初也没有想清楚。然后看了一眼mhy写的题解写了凸壳，秒懂。
二分一个答案，设它是ans。如果ans≥realAns的话，那么就会存在yi-ans*xi+qj-ans*pj≥0。然后i和j就分开了。于是变成了求一条路径上yi-ans*xi的最大值。把xi看作k，把yi看作b，就变成半平面交了。于是开归并式线段树把凸壳给记录下来就好了。然后复杂度大约是单次询问O(lg3(n))的？链剖后每棵树单独建树，然后复杂度我就不会算了TT。
于是就硬着头皮写了，然后发现跑得还挺快。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 30009;
const int maxl = 15;
const int max_buf = maxn * maxl * 2;
const double eps = 1e-6;
const double finf = 1e10;
int ibuf_arr[max_buf], *ibuf(ibuf_arr);
double fbuf_arr[max_buf], *fbuf(fbuf_arr);
struct edge {
int t;
edge *next;
};
struct line {
double k, b;
inline double xCross(const line& a) {
return (a. b - b) / (k - a. k);
}
inline double f(double x) {
return k * x + b;
}
};
line a[maxn << 1];
struct hull {
int t;
int *l;
double *cx;
void init(int x) {
t = 1;
l = ibuf ++;
l[0] = x;
cx = 0;
}
void merge(const hull& x, const hull& y) {
static int stc[maxn];
static double tx[maxn];
t = 0;
for (int i = 0, j = 0, c; i < x. t || j < y. t; ) {
if (i == x. t || (j < y. t && a[x. l[i]]. k > a[y. l[j]]. k))
c = y. l[j ++];
else
c = x. l[i ++];
if (t && fabs(a[c]. k - a[stc[t - 1]]. k) < eps) {
if (a[c]. b >= a[stc[t - 1]]. b)
-- t;
else
continue;
}
while (t > 1 && a[c]. xCross(a[stc[t - 2]]) <= tx[t - 2])
-- t;
if (t)
tx[t - 1] = a[c]. xCross(a[stc[t - 1]]);
stc[t ++] = c;
}
l = ibuf;
ibuf += t;
cx = fbuf;
fbuf += t - 1;
for (int i = 0; i < t; ++ i) {
l[i] = stc[i];
if (i < t - 1)
cx[i] = a[stc[i]]. xCross(a[stc[i + 1]]);
}
}
double qry(double x) {
int p(lower_bound(cx, cx + t - 1, x) - cx);
return a[l[p]]. f(x);
}
};
struct seg {
hull h[2];
int l, r;
seg *ls, *rs;
};
int n, m;
double qans[2], qx;
int fa[maxn], d[maxn], sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn], *ci[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
seg slst[maxn << 2], *sp(slst), *rt[maxn];
inline void upMax(double& a, double b) {
if (a < b)
a = b;
}
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}
#define cpos(_p_) (d[_p_]-d[ch[fc[_p_]]])
#define midp(p) ((p->l+p->r)>>1)
inline seg* sgtBuild(int l, int r, int* ci) {
seg *p(sp ++);
p-> l = l;
p-> r = r;
if (l + 1 == r) {
p-> h[0]. init(ci[l]);
p-> h[1]. init(ci[l] + n);
}
else {
p-> ls = sgtBuild(l, midp(p), ci);
p-> rs = sgtBuild(midp(p), r, ci);
p-> h[0]. merge(p-> ls-> h[0], p-> rs-> h[0]);
p-> h[1]. merge(p-> ls-> h[1], p-> rs-> h[1]);
}
return p;
}
inline void sgtQry(seg* p, int l, int r) {
if (p-> l == l && p-> r == r) {
upMax(qans[0], p-> h[0]. qry(qx));
upMax(qans[1], p-> h[1]. qry(qx));
}
else if (r <= midp(p))
sgtQry(p-> ls, l, r);
else if (l >= midp(p))
sgtQry(p-> rs, l, r);
else {
sgtQry(p-> ls, l, midp(p));
sgtQry(p-> rs, midp(p), r);
}
}
void divide() {
static int q[maxn];
int hd(0), tl(1);
memset(d, 0, sizeof(d));
d[q[0] = 1] = 1;
fa[1] = 0;
while (hd < tl) {
int p(q[hd ++]);
for (edge* e = head[p]; e; e = e-> next)
if (!d[e-> t]) {
d[e-> t] = d[p] + 1;
fa[e-> t] = p;
q[tl ++] = e-> t;
}
}
tc = 0;
for (int i = tl - 1; i >= 0; -- i) {
int p(q[i]), z(-1);
sz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (fa[e-> t] == p) {
sz[p] += sz[e-> t];
if (z == -1 || sz[e-> t] > sz[z])
z = e-> t;
}
if (z == -1)
cl[fc[p] = ++ tc] = 1;
else
++ cl[fc[p] = fc[z]];
ch[fc[p]] = p;
}
for (int i = 1; i <= tc; ++ i) {
ci[i] = ibuf;
ibuf += cl[i];
}
for (int i = 1; i <= n; ++ i)
ci[fc[i]][cpos(i)] = i;
for (int i = 1; i <= tc; ++ i)
rt[i] = sgtBuild(0, cl[i], ci[i]);
}
bool check(int u, int v, double x) {
qans[0] = qans[1] = -finf;
qx = -x;
while (fc[u] ^ fc[v])
if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
sgtQry(rt[fc[u]], 0, cpos(u) + 1);
u = fa[ch[fc[u]]];
}
else {
sgtQry(rt[fc[v]], 0, cpos(v) + 1);
v = fa[ch[fc[v]]];
}
if (d[u] < d[v])
sgtQry(rt[fc[u]], cpos(u), cpos(v) + 1);
else
sgtQry(rt[fc[u]], cpos(v), cpos(u) + 1);
return qans[0] + qans[1] >= 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
scanf("%lf", &a[i]. k);
for (int i = 1; i <= n; ++ i)
scanf("%lf", &a[i]. b);
for (int i = 1; i <= n; ++ i)
scanf("%lf", &a[i + n]. k);
for (int i = 1; i <= n; ++ i)
scanf("%lf", &a[i + n]. b);
memset(head, 0, sizeof(head));
for (int i = 1; i < n; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
divide();
scanf("%d", &m);
while (m --) {
int u, v;
scanf("%d%d", &u, &v);
double l(1e-8), r(1e8);
while (l + eps < r) {
double mid((l + r + eps) / 2.0);
if (check(u, v, mid))
l = mid;
else
r = mid - eps;
}
printf("%.4lf\n", l);
}
}
