自动搬运

查看原文

来自洛谷，原作者为

	Krimson 别祈祷

搬运于2025-08-24 22:25:51，当前版本为作者最后更新于2021-11-15 22:03:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简述题意

给定一棵树，每个点有一个权值 $a_{u}$ ，每次新经过一个没有到达过的点 $u$ 则会令当前的 $HP \leftarrow HP+a_{u}$。

询问从 $1$ 出发能否到达 $t$ ，并且任意时刻 $HP\geq 0$。

Solution

一道经典题了，唯一的印象就是去年 hehezhou 讲过，但是当时还太菜听不懂，现在回来补一下。

考虑直接做 DP ，设 $f_{u,i}$ 表示以 $i$ 的血量进入子树 $u$ 中最多可以获得 $f_{u,i}$ 的血量。

至于判断是否能到达 $t$ ，就新加入一个权值为 $+\infty$ 的点连接在 $t$ 上，最后看 $f_{1,0}$ 是否为 $+\infty$ 即可。

$f_{u}$ 虽然查询快，但是修改是 $O(W)$ 的，而我们只需要查询一次。

同时，即使使用线段树维护，也不太方便实现两个 $f$ 数组之间的合并，因为要考虑到可能在两个子树间 “反复横跳” 的情况。

因此，我们尝试用另一种方法来得到 $f_{u}$ ，设 $g_{u}$ 为若干个二元组 $(x,y)$ 的集合，表示如果当前血量 $\geq x$ ，则可以再额外加上 $y$ 。（这个东西和 $f_{u}$ 的差分数组很像不过并不完全一样）

那么原来的 $f_{u,i}$ 就变成了这样一个过程：

• 初始令 $HP=i$
• 取出当前 $g_{u}$ 中 $x$ 最小的那个二元组 $(x,y)$ ，如果 $HP>x$ 就结束，否则让 $HP \leftarrow HP+y$ ，并删掉二元组 $(x,y)$
• 重复上述步骤

最后得到的 $HP$ 就是 $f_{u,i}+i$ 。

这样子虽然查询一次的复杂度变高了，但是合并就方便了，考虑如何合并两颗子树 $p,q$ ，实际上就是把两个集合给合并起来。

那么现在要把 $u$ 加入到这个子树合并而成的集合中，该如何操作？

1. $a_{u} > 0$

   直接往当前集合中丢入一个 $(0,a_{u})$

2. $a_{u}<0$

我们令 $cur$ 表示以当前 $HP$ 状态下能额外提供的血量为 $cur$ ，$L$ 表示如果要进入子树 $u$ ，初始的 $HP$ 至少应该为多少。

• 初始令 $cur=a_{u},L=-a_{u}$，表示初始至少有 $-a_{u}$ 的血才能进入，能够额外得到 $a_{u}$ 的血量。
• 取出最小的二元组 $(x,y)$
• 如果 $x\leq L \or cur < 0$ ，就令 $L\leftarrow\max(L,x-cur),cur\leftarrow cur+y$
• 重复上述操作直到集合为空或者不满足条件
• 如果最后 $cur>0$ ，就往集合中加入二元组 $(L,cur)$

这样做是考虑我们初始的状态对这个集合的影响。

如果 $L\geq x$ ，那么二元组 $(x,y)$ 一定会被统计上，同时如果初始 $HP$ 在 $[x,L)$ 之间则不应该得到二元组 $(x,y)$ 的贡献，因此直接将 $(x,y)$ 附加到初始状态上，变成一个新的子问题。

如果 $cur<0$ ，光拿 $HP\geq L$ 的这一部分一定不优，肯定是还拿了集合里的其他二元组，因此继续将二元组附加到初始状态上直到 $cur\geq 0$ 为止。

可以发现我们每次查询的都是集合里最小值，因此可以用堆来维护，最后只需要查询一下 $f_{1,0}$ 。

如果使用左偏树来维护堆是 $O(n\log n)$ 的，当然直接用 STL 外加启发式合并也可以通过此题，而且比较好写。

Code

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long 
#define ri int
#define pll pair<ll,ll>
const int MAXN=2e5+7;
const ll inf=1e18;
int n,t;
ll a[MAXN];
vector<int> g[MAXN];
priority_queue<pll,vector<pll>,greater<pll> > q[MAXN];
void merge(priority_queue<pll,vector<pll>,greater<pll> > &p,priority_queue<pll,vector<pll>,greater<pll> > &q){
    if(p.size()<q.size()) p.swap(q);
    while(!q.empty()) p.push(q.top()),q.pop();
}
void dfs(int u,int fa){
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        merge(q[u],q[v]);
    }
    if(a[u]>0) q[u].push((pll){0,a[u]});
    if(a[u]<0){
        ll cur=a[u],L=-cur;
        while(!q[u].empty()&&(cur<0||q[u].top().first<(L))) L=max(L,q[u].top().first-cur),cur+=q[u].top().second,q[u].pop();
        if(cur>0) q[u].push((pll){L,cur});
    }
}
void work(){
    scanf("%d%d",&n,&t);
    for(ri i=1;i<=n+1;++i) g[i].clear();
    for(ri i=1;i<=n;++i) scanf("%lld",a+i);
    for(ri i=1;i<n;++i){
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v),g[v].push_back(u);
    }
    ++n;
    for(ri i=1;i<=n;++i) while(!q[i].empty()) q[i].pop();
    g[n].push_back(t),g[t].push_back(n);a[n]=inf;
    dfs(1,0);
    ll hp=0;
    while(!q[1].empty()&&hp>=q[1].top().first){
        hp+=q[1].top().second;
        q[1].pop();
    }
    if(hp*2>=inf) puts("escaped");
    else puts("trapped");
}
int main(){
    int T;cin>>T;while(T--) work();
}