题解 【P7011 [CERC2013]Escape】
command_block
2021-10-19 19:38:48
**题意** ： 有一棵 $n$ 个顶点的树，点 $u$ 有权值 $w_u$ 。
初始时玩家在顶点 $1$ ，游戏目标是到达顶点 $t$ 。
记玩家血量为 $H$ ，初始为 $0$ 。第一次到达顶点 $u$ 时，令 $H\leftrightarrow H+w_u$ ，若此时 $H<0$ ，（无论 $u$ 是否是终点）则游戏失败。
判断游戏是否能成功。
多组数据，$n\leq 2\times 10^5,\sum n\leq 5\times10^5$ 。
------------
将 $1$ 视为根。
观察可能的策略：当你血少的时候，可能无法越过某些节点，要在一些分支赚到足够的血，然后越过之前无法越过的点，在其子树获取更多的血，不断重复……确实很像闯关变强的过程。
为了统一问题，为 $t$ 添加一个子节点 $t'$ ，令 $w_{t'}=\infty$ ，则问题变为判定最后 $H$ 是否能变为无穷大。
对于某个子树，我们**只关心**以 $a$ 的血量进入能赚多少血量。
记 $f_{u,a}$ 表示以 $a$ 的初始血量进入 $u$ 最终最多能获得的血量。显然 $f_{u,a}-a$ （赚的差值）随 $a$ 单调不减。
最后查看 $f_{1,0}$ 是否为无穷大即可。
考虑：若我们得到了各个子树的 $f$ ，如何求出本树的 $f$ 。
对于两种子树，若他们的 $f$ 相同，则是等效的。
我们可以根据 $f$ 构造等效双层菊花图，第 $i$ 个分支权值为 $\longrightarrow(-i-f_{u,i-1})\longrightarrow(+f_{u,i})$ 。
不难发现，若初始权值为 $i$ ，走且仅能前 $i$ 个分支，最终权值为 $f_{u,i}$ 。
注意到当 $f_{u,i-1}=f_{u,i}$ （即 $f_{u,i}$ 不为前缀最大值时），分支 $i$ 没有收益，可以删去。
我们可以进一步以二元组集合 $\{(a,f_{u,a})|f_{u,a}\text{为前缀最大值}\}$ 描述双层菊花图，代表初始有 $a$ 的血量就能达到 $f_{u,a}$ 的血量。
可以发现，此时剩余的区间 $[a,f_{u,a}]$ 互不相交。
考虑两个双层菊花图的合并，先令根节点的权值为 $0$。不难发现，相当于简单地将两个双层菊花图的根重合。
使用启发式合并，接下来只需分析单点插入。
插入一对 $(a,b)$ 后，区间可能相交。若区间 $[a,b],[a',b']$ 满足 $a'\in [a,b]$ ，则将两者删除并插入 $[a,b+b'-a']$ ，即合并。
这可以用 `std::map` 维护。
接下来考虑根节点 $w_u$ 的权值。
若 $w_u>0$ ，则相当于插入一个分支 $(0,+w_u)$ 。
若 $w_u<0$ ，记 $k=-w_u$ 。（即“门票”的存在）
按 $a$ 从小到大考虑分支 $(a,b)$ ：若 $b-a\leq k$ ，则 $k\leftarrow k-(b-a)$ （走这个分支赚的钱不够付门票），并删除 $(a,b)$ ；若 $b-a>k$ ，则 $a\leftarrow a+k$ ，$k=0$ ，结束。
复杂度为 $O(n\log^2n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#define Pr pair<ll,ll>
#define mp make_pair
#define fir first
#define sec second
#define Itor map<ll,ll>::iterator
#define pb push_back
#define ll long long
#define MaxN 200500
using namespace std;
const ll INF=1ll<<60;
map<ll,ll> f[MaxN];
vector<int> g[MaxN];
ll w[MaxN];
void insert(int u,Pr now)
{
Itor it2;bool fl=1;
while(1){
it2=f[u].upper_bound(now.fir);
if (it2==f[u].begin())break;
it2--;
if (it2->fir>=it2->sec)f[u].erase(it2);
else {
if (now.fir<=it2->sec)
{it2->sec+=now.sec-now.fir;fl=0;}
break;
}
}if (fl)it2=f[u].insert(now).fir;
while(1){
Itor it3=it2;it3++;
if (it3==f[u].end()||it2->sec<it3->fir)break;
it2->sec+=it3->sec-it3->fir;
f[u].erase(it3);
}
}
void dfs(int u,int fa)
{
int t=0;
for (int i=0,v;i<g[u].size();i++)if ((v=g[u][i])!=fa){
dfs(v,u);
if (!t){t=v;continue;}
else {
if (f[t].size()<f[v].size())swap(t,v);
for (Itor it=f[v].begin();it!=f[v].end();it++)
insert(t,*it);
}
}
if (t)swap(f[u],f[t]);
if (w[u]>0)insert(u,mp(0,w[u]));
if (w[u]<0){
ll det=-w[u];
while(!f[u].empty()&&f[u].begin()->sec<=f[u].begin()->fir+det){
det-=f[u].begin()->sec-f[u].begin()->fir;
f[u].erase(f[u].begin());
}
if (det>0&&!f[u].empty()){
Pr now=*f[u].begin();now.fir+=det;
f[u].erase(f[u].begin());f[u].insert(now);
}
}
}
void solve()
{
int n,t;
scanf("%d%d",&n,&t);
for (int i=1;i<=n;i++)scanf("%lld",&w[i]);
w[n+1]=INF<<1;g[n+1].pb(t);g[t].pb(n+1);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}
dfs(1,0);
puts(
!f[1].empty()&&f[1].begin()->fir==0&&f[1].begin()->sec>INF ?
"escaped" : "trapped"
);
for (int i=1;i<=n+1;i++)
{g[i].clear();f[i].clear();}
}
int main()
{
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
```
进一步注意到，我们需要查询的只有“较小一端”的 $f$ ，于是可以改用小根堆维护合并（不考虑未访问的 $f$ 的合并），再用可并堆维护，复杂度可降为 $O(n\log n)$。