1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
| #include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 30001;
struct Edge
{
int v;
Edge *next;
} g[MAXN*2], *header[MAXN];
void AddEdge(const int x, const int y)
{
static int LinkSize = 0;
Edge* const node = g+(LinkSize++);
node->v = y;
node->next = header[x];
header[x] = node;
}
struct Point
{
double x, y;
Point() { }
Point(const double a, const double b): x(a), y(b) { }
};
inline bool operator<(const Point& lhs, const Point& rhs) { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y); }
const Point O(0, 0);
inline double cross(const Point& A, const Point& B, const Point& C, const Point& D)
{
const double x1 = B.x-A.x, y1 = B.y-A.y;
const double x2 = D.x-C.x, y2 = D.y-C.y;
return x1*y2-x2*y1;
}
//------Segment Tree
struct Segment { Point *Q; int tail; };
Point point[2][MAXN], _memory[MAXN*32], *_memory_top = _memory;
Segment s[2][MAXN*4];
int _t, _st, _ed, n, m, pos[2][MAXN];
double _k;
double _query(const int p, const int lef, const int rig)
{
if (_st <= lef && rig <= _ed)
{
Point *Q = s[_t][p].Q;
int l = 0, r = s[_t][p].tail-1;
while (l <= r)
{
const int m = (l+r)/2;
if (cross(Q[m], Q[m+1], O, Point(1, _k)) >= -1e-6) r = m-1;
else l = m+1;
}
return Q[l].x * _k - Q[l].y;
}
const int mid = (lef+rig)/2;
double res = 1e10;
if (_st <= mid) res = _query(p*2, lef, mid);
if (mid+1 <= _ed) res = std::min(res, _query(p*2+1, mid+1, rig));
return res;
}
inline bool cmp(const int lhs, const int rhs) { return point[lhs] < point[rhs]; }
void Build(const int p, const int lef, const int rig)
{
static int tmp[2][MAXN];
const int mid = (lef+rig)/2;
if (lef != rig)
{
Build(p*2, lef, mid);
Build(p*2+1, mid+1, rig);
}
for (int t = 0; t < 2; ++t)
{
for (int i = lef, l1 = lef, l2 = mid+1; i <= rig; ++i)
if (l2 > rig || (l1 <= mid && point[t][pos[t][l1]] < point[t][pos[t][l2]])) tmp[t][i] = pos[t][l1++];
else tmp[t][i] = pos[t][l2++];
memcpy(pos[t]+lef, tmp[t]+lef, sizeof(*tmp[t])*(rig-lef+1));
Point *&Q = s[t][p].Q;
int& tail = s[t][p].tail;
Q = _memory_top, tail = -1, _memory_top += rig-lef+1;
for (int i = lef; i <= rig; ++i)
{
while (tail >= 1 && cross(Q[tail], Q[tail-1], Q[tail], point[t][pos[t][i]]) <= 1e-6) --tail;
Q[++tail] = point[t][pos[t][i]];
}
}
}
inline double Query(const int t, const int lef, const int rig, const double k)
{
_t = t, _st = lef, _ed = rig, _k = k;
return _query(1, 1, n);
}
//------Heavy Light Decomposition
typedef int Array[MAXN];
Array number, dfn, hson, top, parent, depth, size;
void dfs1(const int u)
{
size[u] = 1;
for (Edge *e = header[u]; e; e = e->next)
if (e->v != parent[u])
{
parent[e->v] = u;
depth[e->v] = depth[u]+1;
dfs1(e->v);
size[u] += size[e->v];
if (size[e->v] > size[hson[u]])
hson[u] = e->v;
}
}
void dfs2(const int u, const int tp)
{
static int timestamp;
number[u] = ++timestamp, dfn[timestamp] = u, top[u] = tp;
if (hson[u])
dfs2(hson[u], tp);
for (Edge *e = header[u]; e; e = e->next)
if (e->v != parent[u] && e->v != hson[u])
dfs2(e->v, e->v);
}
double query(int a, int b, double k)
{
double ans0 = 1e10, ans1 = 1e10;
for (int ta = top[a], tb = top[b]; ta != tb; a = parent[ta], ta = top[a])
{
if (depth[ta] < depth[tb])
std::swap(ta, tb), std::swap(a, b);
ans0 = std::min(ans0, Query(0, number[ta], number[a], k));
ans1 = std::min(ans1, Query(1, number[ta], number[a], k));
}
if (depth[a] > depth[b]) std::swap(a, b);
ans0 = std::min(ans0, Query(0, number[a], number[b], k));
ans1 = std::min(ans1, Query(1, number[a], number[b], k));
return ans0+ans1;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lf", &point[0][i].x);
for (int i = 1; i <= n; ++i) scanf("%lf", &point[0][i].y);
for (int i = 1; i <= n; ++i) scanf("%lf", &point[1][i].x);
for (int i = 1; i <= n; ++i) scanf("%lf", &point[1][i].y);
for (int i = 1, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
AddEdge(x, y);
AddEdge(y, x);
}
dfs1(1);
dfs2(1, 1);
for (int i = 1; i <= n; ++i) pos[0][i] = pos[1][i] = dfn[i];
Build(1, 1, n);
scanf("%d", &m);
for (int i = 0, x, y; i < m; ++i)
{
scanf("%d%d", &x, &y);
double lef = 0, rig = 1e10;
while (rig-lef > 1e-8)
{
const double mid = (lef+rig)/2;
if (query(x, y, mid) >= -1e-6) rig = mid;
else lef = mid;
}
printf("%.4f\n", rig);
}
}
|
