UVALive 6584 Escape (Regionals 2013 >> Europe

题目

给出一棵树，每个节点有一个怪物或血药，遇到怪物必须打，打完后扣掉一定的血量。
一开始英雄的血量为(0)，当血量小于(0)时就挂了。
给出英雄的起点和终点，问能否成功到达终点。

算法

这题的方法真的是太美妙了！感觉ACM的题目比OI的好多了，因为它的程序不长，并且每题都不容易想啊。

我们先来解决一个弱化版问题：把起点作为根，问英雄最多能加多少血。

我们可以想象每个点有一个礼包，这个礼包有两个属性，不妨用((a,b))表示，表示当英雄的血量不少于(a)时可以加上(b)点血量（(b)是负数就减血量）。但是有些限制，如果要取某个礼包，那么它的所有祖先上的礼包都必须先取。

我们现在尝试对每棵子树维护一些礼包，首先要保证所有的礼包都是奖励的。我们不妨假设现在对于点(v)，要根据它的所有儿子(u_i)的礼包合成点(v)子树的礼包。对于点(v)，如果它有怪物，我们就要想办法通过提高(a)使得(b)变为非负数（提高(a)是为了取子树的礼包），如果不行，那么这棵子树是不可能走进去的（因为走进去就一定扣血啊）。

通过提高(a)的值，现在我们成功地在点(v)已经生成了一个礼包，如此下去，我们对于根就生成了一棵礼包树，每个点都是有奖励的！我们就贪心（先选(a)最小的）往下走就好了，这个贪心的话，可以用一个左偏树来维护礼包。每开启一个礼包，就把这个礼包的儿子也加进去。

解决了这个弱化版问题后，剩下的就简单了。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long i64;

const int MAXN = (int) 2e5 + 3;

int n, target;
int A[MAXN];

struct Node{
	Node* s[2];
	int dis;
	i64 minus, plus;
	
	void init() {
		s[0] = s[1] = NULL;
		dis = 0;
		minus = plus = 0;
	}
};
Node node[MAXN];

struct Edge {
	Edge* next;
	int to;
};

Edge mem[MAXN * 2];
Edge* info[MAXN];
Edge* curMem;

void insert(int a, int b) {
	curMem->to = b;
	curMem->next = info[a];
	info[a] = curMem ++;
}

Node* merge(Node* x, Node* y) {
	if (! x) return y;
	if (! y) return x;
	if (x->minus > y->minus) swap(x, y);
	x->s[1] = merge(x->s[1], y);
	if (x->s[1] ? x->s[1]->dis : 0 > x->s[0] ? x->s[0]->dis : 0) 
		swap(x->s[0], x->s[1]);
	x->dis = x->s[1] ? x->s[1]->dis + 1 : 1;
	return x;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	
	scanf("%*d");
	while (scanf("%d%d", &n, &target) == 2) {
		curMem = mem;
		memset(info, 0, sizeof info);
		for (int i = 1; i <= n; i ++) 
			scanf("%d", A + i);

		for (int i = 1; i < n; i ++) {
			int v, u;
			scanf("%d%d", &v, &u);
			insert(v, u);
			insert(u, v);
		}
		
		static int que[MAXN];
		static int fa[MAXN];
		memset(fa, 0, sizeof fa);
		int low = 0, high = 0;
		que[high ++] = target;
		while (low < high) {
			int v = que[low ++];
			for (Edge* pt = info[v]; pt; pt = pt->next) {
				int u = pt->to;
				if (u != fa[v]) {
					fa[u] = v;
					que[high ++] = u;
				}
			}
		}

		static bool path[MAXN];
		memset(path, 0, sizeof path);
		for (int v = 1; v != 0; v = fa[v]) 
			path[v] = true;
			
		for (int i = high - 1; i > 0; i --) {
			int v = que[i];
			if (path[v]) continue;
			
			Node* son = NULL;
			for (Edge* pt = info[v]; pt; pt = pt->next) 
				if (! path[pt->to] && pt->to != fa[v])
					son = merge(son, &node[pt->to]);
			
			Node* cur = node + v;
			cur->init();
			cur->minus = max(0, - A[v]);
			cur->plus = A[v];
			
			while (son && (cur->plus < 0 || cur->minus > son->minus)) {
				if (cur->plus < 0) {
					cur->minus = max(cur->minus, son->minus - cur->plus);
					cur->plus += son->plus;
				}
				else {
					cur->plus += son->plus;
				}
				son = merge(son->s[0], son->s[1]);
			}
			
			cur = merge(cur, son);
			if (cur->plus < 0) cur = NULL;
		}
		
		i64 hp = 0;
		bool ok = true;
		Node* tree = NULL;
		for (int v = 1; v != 0; v = fa[v]) {
			hp += A[v];
			if (hp < 0) {
				ok = false;
				break;
			}
			for (Edge* pt = info[v]; pt; pt = pt->next) {
				int u = pt->to;
				if (path[u]) continue;
				if (u == fa[v]) continue;
				tree = merge(tree, &node[u]);
			}
			while (tree && hp >= tree->minus) {
				hp += tree->plus;
				tree = merge(tree->s[0], tree->s[1]);
			}
		}
		
		if (ok) printf("escaped
");
		else printf("trapped
");
	}
	
	return 0;
}