(*2700) ICM Technex 2018 and Codeforces Round 463 (Div. 1 + Div. 2, combined) F. Escape Through Leaf

原题链接：https://codeforces.com/contest/932/problem/F

F. Escape Through Leaf

题目描述

有一颗$n(2\le n \le 10^5)$个节点的树，根节点为$1$，每个节点上都有两个值与它关联，记第$i$个节点上的两个值分别为$a_i,b_i(-10^5\le a_i,b_i\le10^5)$，你可以从某个节点跳到以它为根的子树的任意节点上，从$x$节点跳到$y$节点的代价为$a_x*b_y$，对于每个节点，计算跳转到任何一个叶子节点最小的代价；注意：1.根节点不可能是叶子节点；2.叶子几点本身的代价为$0$

输入格式

第1行：$n$

第2行，空格分隔：$a_1\ a_2\ ...\ a_n$

第3行，空格分隔：$b_1\ b_2\ ...\ b_n$

接下来共$n-1$行，表示$u,v$节点有一条边：

$u_1\ v_1$

…

$u_i\ v_i$

…

$u_n\ v_n$

输出格式

输出一行，空格分隔的每个节点的最小代价

示例

输入

3
2 10 -1
7 -7 5
2 3
2 1

输出

10 50 0 

说明

节点1为根节点，节点3为叶节点；1节点直接跳到3节点代价最小，为$2*5=10$；2节点只有一种方法跳到3节点，代价为$10*5=50$；3节点已经是叶节点，代价为$0$

解决方案

记节点$i$的最小代价为$dp[i]$，我们可以得到递推式：$dp[i]=min_{j\in subtree(i)}(a[i]*b[j]+dp[j])$，如果采用朴素的暴力搜索的方法，时间复杂度是$O(n^2)$，无法满足我们的需求，因此我们需要寻找一种快速求出该递推式最大值的方法，利用凸包技巧Convex Hull Trick，我们可以在所有的$dp[j],b[j]$都存放到凸包数据结构中时，通过$O(logn)$的时间复杂度得到$dp[i]$，现在的问题是，如果直接按顺序将子树中的数据添加到凸包中，则总的时间复杂度仍然是$O(n^2)$，在合并子树的过程中，我们可以采取将节点数量少的数据列表合并到节点数量多的数据列表中，我们考虑某个节点，第一次将其添加到某个数据列表中的时间为$O(1)$，假设当前的列表长度为$x$，则下次合并的列表长度必定$\ge x$，合并后的长度$\ge 2*x$，可以观察到，每次合并后所处列表的长度至少会加倍，而列表的最大长度为$n$，因此对于任意一个节点，合并的次数$\le log(n)$，因此对于所有的节点，总的时间复杂度为$O(n*log(n))$

时间复杂度

$O(n*log(n))$

代码

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

template<typename T>
struct Line {
    T k, b;
    // 集合中的直线按照斜率从小到大排序，该值表示本直线与下一条直线的交点的横坐标
    mutable T intersect_x;
    bool operator<(const Line<T>& o) const { return k < o.k; }  // 用于按照斜率排序
    bool operator<(T x) const { // 用于在Query时进行二分查找
        return intersect_x < x;
    }                                                  // 用于二分查找
    T Eval(T x) const { return k * x + b; }  // 求直线在x点的y值
    T IntersectX(const Line<T>& line) const { // 求与直线line的交点的横坐标
        assert(k != line.k); // 斜率不能相等，否则除0异常
        return Div(line.b - b, k - line.k);
    }
    T Div(T a, T b) const {
        if constexpr (std::is_integral<T>::value) {
            // floored division,
            // 因为两条直线之间的交点可能是小数，但是x是整数，因此小数部分永远不会取到
            // 所以求直线交点时只需要记录<=交点横坐标值的最大整数即可
            // 3/2 -> 1; -3/2 -> -2; 4/2 -> 2; -4/2 -> 2
            return a / b - ((a ^ b) < 0 && a % b);
        } else {
            return a / b;
        }
    }
};

template <typename T, int FIND_MIN = 0>
class LineContainer {
   public:
    void Add(T k, T b) {
        if (FIND_MIN) Add(Line<T>{-k, -b, 0});
        else Add(Line<T>{k, b, 0});
    }
    // 查找使得k*x+b最大的那条直线并返回最大的k*x+b
    T Query(T x) {
        assert(!lines.empty());
        auto it = lines.begin();
        auto l = lines.lower_bound(x);
        return FIND_MIN ? -(l->Eval(x)) : l->Eval(x);
    }
    size_t Size() {
        return lines.size();
    }
    void Swap(LineContainer<T, FIND_MIN>& other) {
        lines.swap(other.lines);
    }
    void Merge(const LineContainer<T, FIND_MIN>& other) {
        for (auto line : other.lines) {
            Add(line);
        }
    }
   private:
    void Add(const Line<T>& line) {
        auto nxt = lines.insert(line), cur = nxt++, prev = cur;
        // 判断插入的直线后面的直线是否需要删除，如果删除则重新求相邻直线的交点
        while (Intersect(cur, nxt)) nxt = lines.erase(nxt);
        // 判断插入的直线本身是否需要删除，删除的话重新求相邻直线的交点
        if (prev != lines.begin() && Intersect(--prev, cur))
            Intersect(prev, cur = lines.erase(cur));
        // 判断插入的直线前面的那一条直线是否需要删除，删除的话重新求相邻直线的交点
        while ((cur = prev) != lines.begin() &&
               (--prev)->intersect_x >= cur->intersect_x)
            Intersect(prev, lines.erase(cur));
    }
    // 求直线l1与l2的交点横坐标（向下取整），并判断是否需要删除直线l2
    bool Intersect(typename multiset<Line<T>>::iterator l1, typename multiset<Line<T> >::iterator l2) {
        if (l2 == lines.end()) {
            l1->intersect_x = numeric_limits<T>::max();
            return false;
        }
        if (l1->k == l2->k) {
            l1->intersect_x = l1->b > l2->b ? numeric_limits<T>::max()
                                            : numeric_limits<T>::lowest();
        } else {
            l1->intersect_x = l1->IntersectX(*l2);
        }
        return l1->intersect_x >= l2->intersect_x;
    }

    multiset<Line<T>, less<>> lines;
};

class Solution {
public:
    void Solve() {
        int n;
        while(cin>>n) {
            vi a(n), b(n);
            cin>>a>>b;

            vector<vi> edges(n);
            int u,v;
            rep(i,0,n-1) {
                cin>>u>>v;
                u--; v--;
                edges[u].emplace_back(v);
                edges[v].emplace_back(u);
            }

            // dp[i] = min(a[i]*b[j] + dp[j]), j is on the subtree rooted by i
            vector<ll> dp(n, numeric_limits<ll>::max());
            function<void(int, int, LineContainer<ll, 1> &)> dfs =
                [&](int u, int p, LineContainer<ll, 1> &lines) {
                  if (sz(edges[u]) == 1 && edges[u][0] == p) {
                    dp[u] = 0;
                  } else {
                    for (auto v : edges[u]) {
                      if (v == p) continue;
                      LineContainer<ll, 1> tmp;
                      dfs(v, u, tmp);
                      if (tmp.Size() > lines.Size()) lines.Swap(tmp);
                      lines.Merge(tmp);
                    }
                    dp[u] = lines.Query(a[u]);
                  }
                  lines.Add(b[u], dp[u]);
                };

            LineContainer<ll, 1> lines;
            dfs(0, -1, lines);

            rep(i,0,sz(dp)) {
                if (i) cout << " ";
                cout << dp[i];
            }
            cout << endl;

            // cout << fixed << setprecision(9) << ans << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
#if USACO
    set_io("time");
#else
    set_io("tmp");
#endif
    Solution().Solve();

    return 0;
}