地址：http://codeforces.com/gym/100299(要登录了点进gym才能成功传送)
很有意思的一个Problem。
一棵树上，勇者在1号点，初始血量是0。每个点有一个权值，踩上去血量会加上$$delta_i$$，这个值可正可负。勇者任何时候血量不能低于0。问勇者能否到达某个目标点T。
国际惯例$$1 \leq n \leq 10^5, -10^6 \leq delta_i \leq 10^6$$
看了solution以后才写出来的。
其实看之前已经有一些零零碎碎的idea。就是组织不起来。
- 按道理可以把结果组织成带拓扑关系的pair的形式。pair的第一个元素表示至少要多少血量才能进去，第二个元素表示进去以后能增加多少血量。通俗说就是每个血泉的门槛。
- 进去以后血量会更亏的地方没有必要走进去
- 应该转化成最多能获得多少血量的问题。
先看最后一点，转化的方法是从需要到达的点连一条边到一个新的点，这个新的点值是无穷。最后只要看最多能获得的血量是不是达到无穷就行了。
然后剩下的就是solution最神棍的地方。在求解“最多能获得多少血量”的前提下，因为最优性的原则可以把一棵树化归为一种理想结构：拓扑关系为一条链的pair。并且满足上面提到的第2条(即每对pair里加血总比扣血多)，以及依赖越浅的pair，门槛越低。也就是说，把他看成数组的话，门槛递增。
证明分两步。
-
证明：假设是一条链的依赖关系，那么可以视作以上提到理想结构。
- 显然一条链上相邻的正值和相邻的负值可以合并。于是必然正负交错，可以构成pair。
- 依赖关系最深的pair(就是最后一个)，如果first >= second，那么可以直接扔掉。因为根据最优性，永远不会选它。
- 对于相邻的pair，如果previous.first >= previous.second(扣血比补血多)，那么这个pair必然可以和后面一个合并。原因是根据最优化目标的原则，不可能取了previous就不取next。所以previous和next要么同取要么同不取，所以理应合并。
- 对于相邻的pair，如果previous.first >= next.first(伤血门槛不递增)，那么previous和next必然可以合并。原因是：根据前面两条，所有的pair都满足first < second，所以根据最优性能取都取掉最好。所以都是贪心去取就好了。如果next门槛比previous还低，那么做完previous肯定顺便做掉next。其实这里条件可以更紧一点，取previous.first >= preivous.first – previous.second + next.first作为合并条件也可以AC的，但是前面那个已经足够了。
-
证明：假如每个分支下的子树都是链，那么该子树也可以看成链。
其实就是数学归纳法的意思。然后这个只要把每个分支下的pair按first顺序列成一行就可以了。
综上，用multiset<pair <long long, long long>>维护链就可以了。
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PLL;
typedef multiset <PLL> MS;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define foreach(it,v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
const int N = 200005;
const ll INF = 1e15;
int Tc, n, m;
vector <int> E[N];
MS pool[N];
ll a[N];
MS* merge(MS *a, MS *b) {
if (a->size() < b->size()) swap(a, b);
foreach (it, *b) a->insert(*it);
b->clear();
return a;
}
MS* dfs(int u, int fa) {
MS *res = &pool[u];
rep (i, E[u].size())
if (E[u][i] != fa)
res = merge(dfs(E[u][i], u), res);
PLL cur = a[u] > 0 ? PLL(0, a[u]) : PLL(-a[u], 0);
while (!res->empty() && (cur.second < cur.first || cur.second >= res->begin()->first)) {
PLL tmp = *res->begin();
res->erase(res->begin());
cur = tmp.first > cur.second ? PLL(cur.first - cur.second + tmp.first, tmp.second) : PLL(cur.first, cur.second - tmp.first + tmp.second);
}
if (cur.second > cur.first) res->insert(cur);
return res;
}
int main() {
scanf("%d", &Tc);
while (Tc--) {
scanf("%d%d", &n, &m);
rep (i, n + 1) E[i].clear();
rep (i, n) {
int x;
scanf("%d", &x);
a[i] = x;
}
rep (i, n - 1) {
int u, v;
scanf("%d%d", &u, &v);
u--; v--;
E[u].push_back(v);
E[v].push_back(u);
}
--m;
E[m].push_back(n);
E[n].push_back(m);
a[n++] = INF;
MS *res = dfs(0, -1);
ll hp = 0;
bool flag = 0;
foreach (it, *res) if (hp >= it->first) {
hp += it->second - it->first;
if (hp >= INF / 2) flag = 1;
}
res->clear();
puts(flag ? "escaped" : "trapped");
}
return 0;
}
![100 \leq a[i] \leq 300](https://s0.wp.com/latex.php?latex=100+%5Cleq+a%5Bi%5D+%5Cleq+300&bg=ffffff&fg=000&s=0&c=20201002)
，每个桶容量300，问最少多少个桶能装完给定的a[i]。