正题
题目链接:https://www.luogu.com.cn/problem/P7011
题目大意
给出\(n\)个点的一棵树，从一出发，要走到 \(t\)。初始时权值为\(0\)，每个节点有一个权值\(w_i\)，第一次走过这个节点时会让权值加上该节点的权值，要求全程权值不能为负数，求能否走到\(t\)。
\(1\leq n\leq 2\times 10^5\)
解题思路
第一个比较麻烦的点是有一个终点的限制，我们走到终点之后就不需要考虑其他点了，不妨在终点后接一个权值为\(+\infty\)的节点，然后问题变为能否遍历全树。
接下来我们会发现有个很麻烦的点，因为对于一个子树我们可能进入多次，一个比较暴力的想法是我们可以设\(f_{x,j}\)表示我们在权值为\(j\)的时候进入\(x\)的子树再出来时能够变为的最大权值。
假设我们权值从\(j\)增加到了\(j+k\)，那么再进入能够获得的贡献就是\(f_{i,j+k}-f_{i,j}\)，不难发现对于一个\(f_{i,j}\)不同的权值个数只有最多子树大小个。考虑维护这些变换的位置，记为若干个二元组\((x,y)\)表示权值为\(x\)时进入能够获得\(y\)的权值，显然的我们有这些区间\([x,x+y]\)是不相交的（因为如果相交那么可以一次获得更多权值）。
而合并的时候我们直接暴力把这些区间合并（因为即使表现上相交了，我们可以后续考虑节点权值的时候再合并这些区间），然后根据节点\(x\)的权值暴力合并前面的区间。
至于两个堆的合并自然可以用可并堆但是不如启发式合并好写。
时间复杂度：\(O(n\log^2 n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N=2e5+10;
struct node{
ll to,next;
}a[N<<1];
ll T,n,t,tot,ls[N],p[N],w[N];
priority_queue<pair<ll,ll> >q[N];
void addl(ll x,ll y){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;return;
}
void dfs(ll x,ll fa){
p[x]=x;
for(ll i=ls[x];i;i=a[i].next){
ll y=a[i].to;
if(y==fa)continue;dfs(y,x);
if(q[p[y]].size()>q[p[x]].size())
swap(p[x],p[y]);
while(!q[p[y]].empty()){
q[p[x]].push(q[p[y]].top());
q[p[y]].pop();
}
}
pair<ll,ll> k=mp(0,w[x]);
while(!q[p[x]].empty()){
pair<ll,ll> z=q[p[x]].top();z.first=-z.first;
if(k.second>=0&&z.first>k.first+k.second)break;
k=mp(max(k.first,z.first-k.second),k.second+z.second);
q[p[x]].pop();
}
k.first=-k.first;
if(k.second>0)q[p[x]].push(k);
return;
}
signed main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&t);tot=0;
for(ll i=1;i<=n+1;i++){
ls[i]=0;
while(!q[i].empty())q[i].pop();
}
for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);
for(ll i=1,x,y;i<n;i++){
scanf("%lld%lld",&x,&y);
addl(x,y);addl(y,x);
}
++n;w[n]=1e18;
addl(t,n);addl(n,t);
dfs(1,0);
if(q[p[1]].empty())puts("trapped");
else{
pair<ll,ll> w=q[p[1]].top();
if(w.first>=0&&w.second>1e17)
puts("escaped");
else puts("trapped");
}
}
return 0;
}