F. Escape Through Leaf 李超线段树+线段树合并

题目大意：（来源：洛谷）

解题思路

很容易能写出dp方程
$dp[u]=min(dp[v]+a[u]\ast b[v])$
可以把b[v]当成直线的k，dp[v]当成b，那么其实就是多条直线，找值最小的那条直线进行赋值
对于这道题有个很优秀的数据结构：李超线段树（涨知识了）
但是还有一点需要添加的是，因为只能从当前子树中找，所以要合并线段树（又涨知识了）
哦，对了还顺便学了动态开点线段树

AC代码：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f
#define endl 'n'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pdi;
const ll maxl = 1e5 + 10;
const ll maxn = 1e5 + 10;
ll n;
ll a[maxn], b[maxn], dp[maxn];
ll cnt = 0;
vector <ll> edge[maxn];
struct L {
    ll k, b;
} line[maxn << 1];
struct seg_tree {
    ll lc, rc, id;
} sgt[maxn << 1];
ll rts[maxn << 1];
ll sgt_cnt = 0;
ll rubbish[maxn << 1], rubbish_cnt;
#define lson sgt[rt].lc
#define rson sgt[rt].rc
ll newpoint() {
    if (rubbish_cnt) return rubbish[rubbish_cnt--];
    return ++sgt_cnt;
}
void deletepoint(ll &rt) { //回收点，节约内存
    sgt[rt].lc = sgt[rt].rc = sgt[rt].id = 0;
    rubbish[++rubbish_cnt] = rt;
    rt = 0;
}
ll cal(ll id, ll x) {
    if (id == 0) return inf;
    return line[id].k * x + line[id].b;
}
void update(ll lc, ll rc, ll &rt, ll l, ll r, ll u) {
    if (!rt) rt = newpoint();
    ll mi = (lc + rc) >> 1;
    if (r < lc || l > rc) return;
    ll v = sgt[rt].id;
    ll resu = cal(u, mi), resv = cal(v, mi);
    if (l <= lc && rc <= r) {
        if (lc == rc) {
            if (resu < resv) sgt[rt].id = u;
            return;
        }
        if (!sgt[rt].id) {
            sgt[rt].id = u;
            return;
        }
        if (line[u].k > line[v].k) {
            if (resu < resv) {
                sgt[rt].id = u;
                update(mi + 1, rc, rson, l, r, v);
            }
            else 
                update(lc, mi, lson, l, r, u);
        }
        else if (line[u].k < line[v].k) {
            if (resu < resv) {
                sgt[rt].id = u;
                update(lc, mi, lson, l, r, v);
            }
            else 
                update(mi + 1, rc, rson, l, r, u);
        }
        else {
            if (line[u].b < line[v].b)
                sgt[rt].id = u;
        }
        return;
    }
    update(lc, mi, lson, l, r, u);
    update(mi + 1, rc, rson, l, r, u);
}
ll merge(ll rt1, ll rt2, ll lc, ll rc) {
    if (!rt1 || !rt2) return rt2 | rt1;
    ll v = sgt[rt1].id, u = sgt[rt2].id;   
    ll mi = (lc + rc) >> 1;    
    ll resu = cal(u, mi), resv = cal(v, mi);
    ll rt;
    ll l1 = sgt[rt1].lc, r1 = sgt[rt1].rc, l2 = sgt[rt2].lc, r2 = sgt[rt2].rc;
    //提前赋值，这样回收节点就不会有影响
    if (lc == rc) {
        if (resv > resu) sgt[rt1].id = u, rt = rt2, deletepoint(rt1);
        else rt = rt1, deletepoint(rt2);
        return rt;
    }
    if (!sgt[rt1].id || resu < resv || resu == resv && line[u].b < line[v].b) sgt[rt1].id = u, rt = rt2, deletepoint(rt1);
    else rt = rt1, deletepoint(rt2);  //赋值，并回收节点
    sgt[rt].lc = merge(l1, l2, lc, mi);//往下进行合并
    sgt[rt].rc = merge(r1, r2, mi + 1, rc);
    if (rt == rt1) update(lc, rc, rt1, -maxl, maxl, u);//说明rt1的id更优，然后用rt2的id来更新剩下的
    else update(lc, rc, rt2, -maxl, maxl, v);//同理
    //因为合并之后只有rt存储的节点有效，另一个节点之后不会再用，所以可以删除
    return rt;//返回更优的值
}
pdi pmin(pdi A, pdi B) {
    if (A.first < B.first) return A;
    else return B;
}
pdi query(ll l, ll r, ll rt, ll k) {
    if (!rt) return {inf, 0};
    if (r < k || k < l) return {inf, 0};
    ll mi = (l + r) >> 1;
    ll res = cal(sgt[rt].id, k);
    if (l == r) return {res, sgt[rt].id};
    return pmin({res, sgt[rt].id}, pmin(query(l, mi, sgt[rt].lc, k), query(mi + 1, r, sgt[rt].rc, k)));
}
void dfs(ll u, ll fa) {
    ll pre = 0;
    for (auto v : edge[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u] = min(dp[u], query(-maxl, maxl, rts[v], a[u]).first);
        rts[u] = merge(rts[u], rts[v], -maxl, maxl);
    }
    if (edge[u].size() == 1 && u != 1)
        dp[u] = 0;
    line[++cnt].k = b[u], line[cnt].b = dp[u];
    update(-maxl, maxl, rts[u], -maxl, maxl, cnt);
}
int main() {
	for (int i = 0; i < maxn; i++)
		dp[i] = inf; 
    cin >> n;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    for (ll i = 1; i <= n; i++)
        cin >> b[i];
    for (ll i = 1; i <= n; i++) rts[i] = i, sgt_cnt++;//赋初值
    ll u, v;
    for (ll i = 1; i < n; i++) {
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, 0);
    for (ll i = 1; i <= n; i++)
        cout << dp[i] << " ";
}

最后

以上就是兴奋羽毛为你收集整理的F. Escape Through Leaf 李超线段树+线段树合并的全部内容，希望文章能够帮你解决F. Escape Through Leaf 李超线段树+线段树合并所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。