BZOJ2402 陶陶的难题II

orz mhy。看mhy的刷题记录成为了我成天的刷题方向了。

其实最初也没有想清楚。然后看了一眼mhy写的题解写了凸壳，秒懂。

二分一个答案，设它是ans。如果ans≥realAns的话，那么就会存在yi-ans*xi+qj-ans*pj≥0。然后i和j就分开了。于是变成了求一条路径上yi-ans*xi的最大值。把xi看作k，把yi看作b，就变成半平面交了。于是开归并式线段树把凸壳给记录下来就好了。然后复杂度大约是单次询问O(lg³⁽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);
	}
}