【BZOJ 2402】陶陶的难题II

Code

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

const int N = 60009;
const double INF = 1e9;
const double EPS = 1e-4;

struct Point{
double x, y;
inline Point() {
}
inline Point(double a, double b):x(a), y(b) {
}
inline bool operator < (const Point &PP) const {
return x < PP.x || (x == PP.x && y < PP.y);
}
inline bool operator == (const Point &PP) const {
return x == PP.x && y == PP.y;
}
inline Point operator - (const Point &PP) const {
return Point(x - PP.x, y - PP.y);
}
inline double operator * (const Point &PP) {
return x * PP.y - y * PP.x;
}
inline double slope() {
return y / x;
}
}d[N][2];

char c = getchar(); int ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void AddEdge(int u, int v) {
static int E = 1;
}

class HeavyLightDecomposition{
int fa[N], sz[N], dep[N], idx[N], hvy[N], top[N];
class SegmentTree{
vector<Point> cvx[N][2];
public:
int num[N], root, ch[N][2];
inline void init() {
build(root, 1, n);
}
inline void update(int l, int r, double a, double *mx) {
query(root, 1, n, l, r, a, mx);
}
private:
inline void query(int w, int l, int r, int L, int R, double a, double *mx) {
if (L <= l && r <= R) {
mx[0] = max(mx[0], cal(cvx[w][0], a));
mx[1] = max(mx[1], cal(cvx[w][1], a));
} else {
int mid = l + r + 1 >> 1;
if (L < mid) {
query(ch[w][0], l, mid - 1, L, R, a, mx);
}
if (R >= mid) {
query(ch[w][1], mid, r, L, R, a, mx);
}
}
}
inline double cal(const vector<Point> &que, double a) {
int l = 0, r = que.size() - 1, mid, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (mid == 0 || (que[mid] - que[mid - 1]).slope() >= a) {
ret = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return -a * que[ret].x + que[ret].y;
}
inline void build(int &w, int l, int r) {
static int cnt = 0;
w = ++cnt;
if (l == r) {
cvx[w][0].push_back(d[num[l]][0]);
cvx[w][1].push_back(d[num[l]][1]);
} else {
int mid = l + r + 1 >> 1;
build(ch[w][0], l, mid - 1);
build(ch[w][1], mid, r);
int ls = ch[w][0], rs = ch[w][1];
cvx[w][0] = Merge(cvx[ls][0], cvx[rs][0]);
cvx[w][1] = Merge(cvx[ls][1], cvx[rs][1]);
}
}
inline vector<Point> Merge(const vector<Point> &c1, const vector<Point> &c2) {
vector<Point> cur, ret;
for (int i = 0; i < (int)c1.size(); i++) {
cur.push_back(c1[i]);
}
for (int i = 0; i < (int)c2.size(); i++) {
cur.push_back(c2[i]);
}
sort(cur.begin(), cur.end());
cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
for (int i = 0; i < (int)cur.size(); i++) {
while ((int)ret.size() > 1) {
int idx = ret.size() - 1;
if ((cur[i] - ret[idx - 1]) * (ret[idx] - ret[idx - 1]) <= EPS) {
ret.pop_back();
} else {
break;
}
}
ret.push_back(cur[i]);
}
return ret;
}
}SGT;
public:
inline void init() {
DFS1(1, 1);
DFS2(1, 1);
SGT.init();
}
inline double query(int u, int v) {
double l = 0, r = INF, ret = 0, mid;
while (r - l > EPS) {
mid = (l + r) * 0.5;
if (judge(u, v, mid)) {
ret = mid;
l = mid;
} else {
r = mid;
}
}
return ret;
}
private:
inline bool judge(int u, int v, double a) {
double mx[] = {-INF, -INF};
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
SGT.update(idx[top[u]], idx[u], a, mx);
u = fa[top[u]];
} else {
SGT.update(idx[top[v]], idx[v], a, mx);
v = fa[top[v]];
}
}
if (dep[u] > dep[v]) {
SGT.update(idx[v], idx[u], a, mx);
} else {
SGT.update(idx[u], idx[v], a, mx);
}
return mx[0] + mx[1] > 0;
}
inline void DFS1(int w, int f) {
fa[w] = f;
sz[w] = 1;
dep[w] = dep[f] + 1;
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != f) {
DFS1(to[i], w);
sz[w] += sz[to[i]];
if (sz[to[i]] > sz[hvy[w]]) {
hvy[w] = to[i];
}
}
}
}
inline void DFS2(int w, int t) {
static int dcnt = 0;
SGT.num[idx[w] = ++dcnt] = w;
top[w] = t;
if (hvy[w]) {
DFS2(hvy[w], t);
}
for (int i = head[w]; i; i = nxt[i]) {
if (to[i] != fa[w] && to[i] != hvy[w]) {
DFS2(to[i], to[i]);
}
}
}
}HLD;

int main() {
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][0].x);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][0].y);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][1].x);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &d[i][1].y);
}
for (int i = 1; i < n; i++) {