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
| #include <iostream>
#include <vector>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;
int n, a[maxn], b[maxn]; ll D;
int c[maxn], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) c[i] = b[i];
sort(c + 1, c + n + 1); cnt = unique(c + 1, c + n + 1) - c - 1;
for (int i = 1; i <= n; ++i) b[i] = lower_bound(c + 1, c + cnt + 1, b[i]) - c;
}
struct Edge {
int to, next, w;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
e[c1].to = v; e[c1].w = w;
e[c1].next = head[u]; head[u] = c1++;
}
#define lc i << 1
#define rc i << 1 | 1
struct Seg {
ll v, t;
} T[maxn * 4];
inline void maintain(int i) {
T[i].v = T[lc].v + T[rc].v;
T[i].t = T[lc].t + T[rc].t;
}
void update(int i, int l, int r, int k, ll v, ll t) {
if (l == r) return T[i].v += v, T[i].t += t, void();
int m = l + r >> 1;
if (k <= m) update(lc, l, m, k, v, t);
else update(rc, m + 1, r, k, v, t);
maintain(i);
}
ll query(int i, int l, int r, ll v) {
if (l == r) return min(v / c[l], T[i].t);
int m = l + r >> 1;
if (v <= T[lc].v) return query(lc, l, m, v);
else return T[lc].t + query(rc, m + 1, r, v - T[lc].v);
}
ll f[maxn], g[maxn];
void dfs(int u, int fa, ll dis) {
update(1, 1, cnt, b[u], 1ll * c[b[u]] * a[u], a[u]);
if (D > 2 * dis) g[u] = query(1, 1, cnt, D - 2 * dis);
ll mx = 0, secmx = 0;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].w; if (v == fa) continue;
dfs(v, u, dis + w);
if (f[v] > mx) secmx = mx, mx = f[v];
else if (f[v] > secmx) secmx = f[v];
}
f[u] = max(g[u], secmx);
if (u == 1) f[u] = max(g[u], mx);
update(1, 1, cnt, b[u], -1ll * c[b[u]] * a[u], -a[u]);
}
int main() { fill(head, head + maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> D;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i]; init_hash();
for (int i = 2; i <= n; ++i) {
int x, y; cin >> x >> y;
add_edge(x, i, y);
} dfs(1, 0, 0); cout << f[1] << "\n";
return 0;
}
|