Codeforces Round #463 F Escape Through Leaf

問題文

http://codeforces.com/contest/932/problem/F

問題概要

問題文が短いので省略

解法

木DPのイメージでやると, 頂点 v に対して dp[v] = min{ a[v] * b[u] + dp[u] } (u は v の子孫) という式が立つので, Convex Hull Trick で求まりそうな形になります.
あとは, 各ノードに対してその部分木に含まれる任意の頂点に対応する直線の式の集合を持てればいいので, dfs していってマージしていきますが, このときマージテクを使うと O(n * (logn)^2) になるので間に合います.

ソースコード

http://codeforces.com/contest/932/submission/35779894

#include <bits/stdc++.h>
using namespace std;
using graph = vector<vector<int>>;
using ll = long long;

using T = ll;
const T id = LLONG_MIN;

vector<T> pos;

struct line {
    T a, b;
    line(T a_ = 0, T b_ = 0) : a(a_), b(b_) {}
    T get(T x) { return a * x + b; }
};

struct node {
    line l;
    node *lch, *rch;
    node(line l_) : l(l_), lch(nullptr), rch(nullptr) {}
};

node* insert(node *p, int lb, int ub, line l) {
    if (!p) return new node(l);
    if (p->l.get(pos[lb]) >= l.get(pos[lb]) && p->l.get(pos[ub - 1]) >= l.get(pos[ub - 1])) return p;
    if (p->l.get(pos[lb]) <= l.get(pos[lb]) && p->l.get(pos[ub - 1]) <= l.get(pos[ub - 1])) {
        p->l = l;
        return p;
    }
    int c = (lb + ub) / 2;
    if (p->l.get(pos[c]) < l.get(pos[c])) swap(p->l, l);
    if (p->l.get(pos[lb]) <= l.get(pos[lb]))
        p->lch = insert(p->lch, lb, c, l);
    else
        p->rch = insert(p->rch, c, ub, l);
    return p;
}

T get(node *p, int lb, int ub, int t) {
    if (!p) return id;
    if (ub - lb == 1) return p->l.get(pos[t]);
    int c = (lb + ub) / 2;
    if (t < c) return max(p->l.get(pos[t]), get(p->lch, lb, c, t));
    return max(p->l.get(pos[t]), get(p->rch, c, ub, t));
}

const int MAX = 1e5;

node* rts[MAX];
int siz[MAX];
vector<line> ls[MAX];

void dfs(int v, int prev, const graph& G, const vector<ll>& a, const vector<ll>& b, vector<ll>& res) {
    siz[v] = 0;
    rts[v] = nullptr;
    for (auto to : G[v]) if (to != prev) {
        dfs(to, v, G, a, b, res);
        if (siz[v] < siz[to]) swap(rts[v], rts[to]), ls[v].swap(ls[to]);
        for (auto& l : ls[to]) {
            rts[v] = insert(rts[v], 0, pos.size(), l);
            ls[v].push_back(l);
        }
        siz[v] += siz[to];
    }
    res[v] = rts[v] ? -get(rts[v], 0, pos.size(), lower_bound(pos.begin(), pos.end(), a[v]) - pos.begin()) : 0;
    ls[v].emplace_back(-b[v], -res[v]);
    rts[v] = insert(rts[v], 0, pos.size(), ls[v].back());
    siz[v] += 1;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    graph G(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v; u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    pos = a;
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    vector<ll> res(n);
    dfs(0, -1, G, a, b, res);
    for (int i = 0; i < n; i++) {
        cout << res[i] << " \n"[i + 1 == n];
    }
    return 0;
}

感想

コンテスト中にこの解法はすぐ思いついたのに, 単調性のない状況で使える Convex Hull Trick を持ってなかったので解けなくて悲しかった….