P7011

· · 题解

简述题意

给定一棵树，每个点有一个权值 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$ 数组之间的合并，因为要考虑到可能在两个子树间 “反复横跳” 的情况。 因此，我们尝试用另一种方法来得到 $f_{u}$ ，设 $g_{u}$ 为若干个二元组 $(x,y)$ 的集合，表示如果当前血量 $\geq x$ ，则可以再额外加上 $y$ 。（这个东西和 $f_{u}$ 的差分数组很像不过并不完全一样） 那么原来的 $f_{u,i}$ 就变成了这样一个过程： - 初始令 $HP=i

最后得到的 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();
}