Gọi ~dp_i~ là chi phí nhỏ nhất để đi từ ~i~ đến một nút lá. Theo đề bài, ta có công thức: ~dp_i = \min_{j \in \text{subtree}(i), j \ne i}(dp_i, dp_j + a_i \cdot b_j)~ với ~\text{subtree}(i)~ là tập các đỉnh trong cây con gốc ~i~. Ta cần tính ~dp_i~ với mọi ~i~ từ ~1~ đến ~n~.

• Subtask 1:

  • Tiến hành DFS từ đỉnh gốc ~1~. Với mỗi ~i~, ta lưu một vector child[i] thể hiện các đỉnh trong cây con gốc ~i~, từ đó ta có thể cập nhật vector child cũng như mảng ~dp~ sau mỗi lần DFS xong từ một nhánh của cây con gốc ~i~.

  • Hoặc đơn giản hơn, ta có thể trải phẳng cây sử dụng Euler Tour, khi đó ta thu được mảng ~t~ là thứ tự topo, và các đoạn ~[\text{tin}_i, \text{tout}_i]~ thể hiện cây con gốc ~i~. Duyệt ngược mảng ~t~, ta thu được công thức ~dp_{t_i} = \min_{j \in [\text{tin}_i, \text{tout}_i]} dp_{t_j} + a_{t_i} \cdot b_{t_j}~.

  • Độ phức tạp: ~O(n^2)~.

• Subtask 2:

  • Cây có dạng đường thẳng ~1-2-\ldots-n~, nên chỉ có nút thứ ~n~ là nút lá.

  • Công thức quy hoạch động giờ đơn giản hơn: ~dp_i = \min_{j>i} (dp_j + a_i \cdot b_j)~, và ~dp_n=0~.

  • Từ công thức quy hoạch động ta thấy cần phải lấy giá trị nhỏ nhất của các đường thẳng dạng ~(b_j \cdot x + dp_j)~ với ~x=a_i~, nên ta sẽ sử dụng Convex Hull Trick để tối ưu. Nhận thấy các hệ số ~b_j~ đã được sắp xếp tăng dần nên khi duyệt ngược từ ~n~ về ~1~, các hệ số của đường thẳng sẽ được sắp xếp giảm dần. Vậy ta chỉ cần sử dụng stack và chặt nhị phân để cài đặt Convex Hull Trick.

  • Độ phức tạp: ~O(n \log n)~.

• Subtask 3:

  • Với mỗi nút trên cây, ta lưu một cấu trúc dữ liệu ~S~ cho phép:

  • Thêm đường thẳng ~(a,b)~ theo thứ tự bất kì.

  • Truy vấn ~\min(ax + b)~ với ~x~ cho trước.

  • Ta có thể sử dụng cấu trúc LineContainer (lưu các đường thẳng bằng set), hoặc cây LiChao. Lưu ý, cây LiChao phải được cài đặt động, nghĩa là chỉ khởi tạo các nút trên cây khi nào ta dùng đến (sử dụng vector hoặc con trỏ)

  • Tiến hành DFS từ đỉnh gốc ~1~. Xét cặp ~(u,v)~ với ~u~ là cha trực tiếp của ~v~, ta sử dụng kĩ thuật small to large: nếu số đường thẳng trong ~S_u~ nhỏ hơn số đường thẳng trong ~S_v~, ta hoán đổi ~S_u~ và ~S_v~. Sau đó, thêm các đường thẳng trong ~S_v~ vào ~S_u~. Sau khi xét hết mọi con trực tiếp ~v~ có thể, thực hiện truy vấn tại điểm ~x=a_u~, và thêm đường thẳng ~(b_u,dp_u)~ vào ~S_u~.

  • Ngoài ra ta cũng có thể cải tiến cách 2 của subtask 1 sử dụng interval tree trên tập đoạn thẳng, với độ phức tạp giữ nguyên.

  • Độ phức tạp: ~O(n \log^2 n)~

#include <bits/stdc++.h>

using namespace std;

namespace std {
#ifndef LOCAL
#define cerr \
  if (0) cerr
#endif
}  // namespace std

using ll = long long;

struct Line {
  mutable ll k, m, p;
  bool operator<(const Line& o) const { return k < o.k; }
  bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
  // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  static const ll inf = LLONG_MAX;
  ll div(ll a, ll b) {  // floored division
    return a / b - ((a ^ b) < 0 && a % b);
  }
  bool isect(iterator x, iterator y) {
    if (y == end()) return x->p = inf, 0;
    if (x->k == y->k)
      x->p = x->m > y->m ? inf : -inf;
    else
      x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  void add(ll k, ll m) {
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p)
      isect(x, erase(y));
  }
  ll query(ll x) {
    assert(!empty());
    auto l = *lower_bound(x);
    return l.k * x + l.m;
  }
};

const int N = 1e5 + 5;

vector<int> g[N];
LineContainer s[N];
int a[N], b[N];
int n;
ll ans[N];

void dfs(int u, int par = -1) {
  for (int v : g[u]) {
    if (v == par) {
      continue;
    }
    dfs(v, u);
    if (s[u].size() < s[v].size()) {
      s[u].swap(s[v]);
    }
    for (auto it : s[v]) {
      s[u].add(it.k, it.m);
    }
  }
  if (!s[u].empty()) {
    ans[u] = -s[u].query(a[u]);
  }
  s[u].add(-b[u], -ans[u]);
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  dfs(1);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  return 0;
}