Luogu7011 [CERC2013] Escape

发表于 更新于 分类于 ， ， 阅读次数：

题意：有一棵 个顶点的树，点 有权值 。

初始时玩家在顶点 ，游戏目标是到达顶点 。

记玩家血量为 ，初始为 。第一次到达顶点 时，令 ，若此时 ，（无论 是否是终点）则游戏失败。

判断游戏是否能成功。

多组数据，，，时限 。

将 视为根。

观察可能的策略：当你血少的时候，可能无法越过某些节点，要在一些分支赚到足够的血，然后越过之前无法越过的点，在其子树赚取更多的血，不断重复……确实很像闯关变强的过程。

为了统一问题，为 添加一个子节点 ，令 ，问题变为判定最后 是否能变为无穷大。

可以猜想，任意子树可以等效为双层菊花图，每个花瓣形如 ， 为进入花瓣的门槛， 为花瓣的收益（一定大于 ）。同时，花瓣的数量（决策段数）是不多的。

一种证明如下：

考虑 DP，记 表示从外部获取的血量为 ，在子树 中能赚的血量。

由于只关心 ，我们可以将任意子树等效为双层菊花图：

  • 第 个花瓣为分支：。
  • 不难发现，若从外部获取血量 ，走且仅能前 个花瓣，最终权值为 。
  • 花瓣数量很多，但有大量花瓣无收益，可以省去。
  • 这样构造出的花瓣是最简的。

将花瓣 记为二元组 。

  • 观察：在最简形式中，所有花瓣对应的 不交。

    证明：若存在 满足：

    • ：仅从 开始可以吃完两个分支，两者可以化简为一个花瓣。
    • ： 更大但获利更少，矛盾。

在树上，先假设根节点的权值为 ，考虑两个子树的合并，也就是将两个菊花的所有花瓣直接加起来。

（花瓣是原问题中已有的模型，它的合并是自然的，这是该思路的最大好处）

进行启发式合并，每次加入一个花瓣。对花瓣集合进行化简。

若存在花瓣 使得 ，若能走花瓣 ，则一定可以走花瓣 ，故可以将两者删除并插入 。不断这样合并，可以使得各个花瓣的 不交。

这可以用 std::map 维护。

接下来考虑根节点 的权值：

  • ：相当于插入一个花瓣 。

  • ，记 。（即“门票”价格）

    按 从小到大考虑花瓣 ：

    • 若 （这个花瓣赚的钱尚不够付门票），令 （将目前累计可以赚的钱从门票中扣除），并删除花瓣 ；
    • 若 （已经足够支付门票），则 ，结束。

复杂度为 。

代码中的 fir 是 ，sec 是 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#define fir first
#define sec second

using ll = long long;
using Pr = std::pair<ll,ll>;
using Itor = std::map<ll,ll>::iterator;
const int MaxN = 200050;
const ll INF = 1ll<<60;

void insert(std::map<ll,ll> &f, const Pr &now) {
	bool flag = true; 
	Itor it = f.upper_bound(now.fir);
	if (it!=f.begin()) {
		it--;
		if (now.fir <= it->fir+it->sec){
			it->sec += now.sec;
			flag = false;
		}
	}
	if (flag)
		it = f.insert(now).fir;
	while(true) {
		Itor it2 = it;
		it2++;
		if (it2==f.end() || it->fir+it->sec < it2->fir)
			break;
		it->sec += it2->sec;
		f.erase(it2);
	}
}

void sub(std::map<ll,ll> &f, ll det) {
	while(!f.empty()) {
		if (f.begin()->sec <= det) {
			det -= f.begin()->sec;
			f.erase(f.begin());
		} else {
			Pr now = *f.begin();
			now.fir += det;
			now.sec -= det;
			f.erase(f.begin());
			f.insert(now);
			break;
		}
	}
}

std::map<ll,ll> f[MaxN];
std::vector<int> g[MaxN];
ll w[MaxN];

void dfs(int u,int fa) {
	int t = 0;
	for (int v : g[u])
		if (v != fa) {
			dfs(v,u);
			if (!t) {t=v; continue;}
			if (f[t].size() < f[v].size())
				std::swap(t,v);
			for (const Pr &now : f[v])
				insert(f[t], now);
		}
	if (t) std::swap(f[u], f[t]);
	if (w[u]>0)
		insert(f[u], std::make_pair(0,w[u]));
	if (w[u]<0)
		sub(f[u], -w[u]);
}

void addLine(int u, int v) {
	g[u].push_back(v);
	g[v].push_back(u);
}

void solve() {
	int N, t;
	scanf("%d%d", &N, &t);
	for (int i=1; i<=N; i++)
		scanf("%lld", &w[i]);
	for (int i=1; i<N; i++) {
		int u,v;
		scanf("%d%d", &u, &v);
		addLine(u, v);
	}
	w[N+1] = 2*INF;
	addLine(t, N+1);

	dfs(1,0);
	if (!f[1].empty() && f[1].begin()->fir==0 && f[1].begin()->sec>INF)
		puts("escaped");
	else 
		puts("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;
}