CEOI 2019 Magic Tree

發表於 更新於 Disqus：

我的作法感覺跟官解差很多，但我覺得蠻精妙的，所以紀錄一下。

題目有點長所以不貼了。

觀察&預處理

觀察一
只有那些有果實的點往上的邊有可能需要被砍，因為不管怎樣的砍法都能規約到只砍那些邊。

甚至可以建一張新圖，新圖只包含有果實的點，每個點的父親為他在原圖上有果實的那些祖先中最淺的點。
注意到新圖的答案跟原圖一樣，因為觀察一的結論。
然後新圖的點數就只會有 $M$ 個。

接下來把所有點照以熟成時間早到晚，如果熟成時間相同則在樹上的深度深到淺，這樣的順序排好，接下來就不用考慮熟成時間是多少了。

觀察二
必定存在最佳解，滿足砍的順序會按照這個順序（子序列）。
可能會因為前面的點已經砍過了導致砍不了後面的點，但是在砍前面的點時則不會被後面的點影響

所以我們接下來就用這個順序來算答案。整個過程就會是多考慮當前點->去改變要不要砍前面的點->重新計算答案。
每次重新計算完的答案就是「考慮前面這些點的最佳解」，所以全部考慮完後的答案就會是最後的答案。

考慮基本情況

假設目前我們考慮的點是 $u$，如果 $u$ 的底下已經有被考慮過的點了，那我們可以先拔那些點再拔 $u$，所以不會怎樣。

但如果 $u$ 的祖先有被考慮過的點（假設他叫 $v$）了，那拔掉 $v$ 後就不能拔 $u$ 了。

接下來讓我們引入一種神奇的思維，令 $a_u$ 為拔掉第 $u$ 個點上面那條邊後的答案，我們的答案會是所有 $a_u$ 的總和。

一開始 $a_u=w_u$，也就是拔掉後我們就能獲得 $w_u$ 的價值。可是 $u$ 跟 $v$ 不能一起拔，所以這時後有兩種情況。

  1. $w_v\le w_u$：拔 $u$ 會比較好，所以把 $a_v$ 給設成 $0$。
  2. $w_v\gt w_u$：拔 $v$ 會比較好，但是拔了 $v$ 就不能拔 $u$，所以讓 $a_v=w_v-w_u$，這樣全部加起來就會是 $w_v$。

我們把第二點這樣減值的情況稱作懲罰，具體來說，$u$ 會給 $v$ 一個 $w_u$ 的懲罰，代表拔了 $v$ 的話會損失多少價值。

注意到懲罰會是單調遞增的（因為你底下的點只會越來越多），所以當懲罰超過了 $w_v$ 時就代表拔 $v$ 點不會比較好，也就是根本不用考慮 $v$ 點了。

一般化作法

每個 $u$ 點維護一個 $pen_u$，代表將那個點身上的懲罰，也就是拔了那個點的話會損失多少價值，一開始 $pen_u=0$，而 $a_u=w_u-pen_u$。

當我們把 $u$ 考慮進來後，令 $cur\_pen$ 為要送給祖先的懲罰，一開始 $cur\_pen=w_u$，接著去往祖先找第一個正在考慮的點 $v$，接下來考慮幾個情況：

  1. 不存在這樣的 $v$：那就不用加懲罰在任何點身上，所以直接結束當前操作。
  2. $w_v-pen_v-cur\_pen\le 0$：代表此時拔這個點不會比較好了，所以不要考慮這個點。也就是把 $a_v$ 設成 $0$，並且把 $pen_v$ 的值都給加進 $cur\_pen$，同時在 $cur\_pen$ 中扣掉 $w_v^\textrm{註 1}$，也就是 $cur\_pen=cur\_pen+pen_v-w_v$，並且再往上找新的 $v$ 重複操作。
  3. $w_v-pen_v-cur\_pen\gt 0$：代表目前的解中，拔掉 $v$ 還是比較好，所以就讓 $a_v=u_v-pen_v-cur\_pen$，並且結束當前操作。

注意到我們的「懲罰」其實就是反悔操作，在當前點的價值大於身上的懲罰時，我們就拔掉這個點，否則就不拔這個點，而反悔成拔他下面那些點。

註 1
為什麼在移除這個點之後要把當前的懲罰扣除自己的價值？這可以看成再反悔的表現，因為拔掉自己跟拔掉下面的點不能同時發生，目前移除當前點是因為我們覺得不拔自己、拔掉下面會比較好。但是之後有可能會有更上面的點帶著很大的價值，這樣的話有可能拔掉下面點會變差（因此就不拔了），那此時不就可以拔掉自己了？
注意到就算那個「更上面的點」拔了的話自己也不能拔，那上面的那個點會帶著自己的懲罰（$pen_v$ 中有著 $w_u$），這樣會抵銷。

再注意到如果已經找不到上面的點了（情況 1），那這樣也不可能有著點會帶著自己的懲罰，所以把當前懲罰給丟掉就只是讓這點造成的貢獻都歸 0，從這個世界被遺忘(?

以下是用 code 說明這段事：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
sort(owo.begin(), owo.end(), [&](auto a, auto b) { return a.first == b.first ? dep[a.second] > dep[b.second] : a.first < b.first; }); // owo 是上面提到的順序
for(const auto &[d, u] : owo) { // 熟成時間, 點編號，這裡不會用到熟成時間了
	int p = u;
	ll cur_pen = arr[u]; // arr[u] 為題目中的 w[u]
	while(true) {
		p = find_first(p); // 往上找到第一個還沒被移除的點
		if(!p) // 找不到沒被移除的點了
			break;
		if(arr[p] - pen[p] - cur_pen <= 0) {
			rem(p); // 移除點 p
			edt(p, 0); // 把 a_p 設成 0
			cur_pen += pen[p] - arr[p];
		}
		else {
			pen[p] += cur_pen;
			edt(p, arr[p] - pen[p]); // 把 a_p 設成 w_p-pen_p-cur_pen
			break;
		}
	}
	edt(u, arr[u]); // 把 a_u 設成 w_u
	add(u); // 開始考慮點 u
}

cout << res << '\n'; // res 為當前的答案

複雜度分析

在以上程式碼，因為每個點只會被加入/移除一次，所以 find_first 會執行 $\mathcal{O}(M)$ 次，而 rem,edt,add 最多執行 $M$ 次。

其中 edt 因為是維護全部的總和而已，所以可以 $\mathcal{O}(1)$。
如果 find_first,edt,add 使用暴力往上找的話複雜度會是 $\mathcal{O}(M)$，此時可以拿到 $M\le 1000$ 的子題。

如果有在考慮的點設成 $1$，還沒考慮/已經移除的設成 $0$，那根到當前點的總和就會是路上有多少正在被考慮的點，這樣就可以二分搜第一個總和改變的祖先在哪裡，配合樹壓平作到 $\mathcal{O}(\log M)$ 查詢，find_first, edt, add 的複雜度就能壓成 $\mathcal{O}(\log^2 M)$。

總複雜度 $\mathcal{O}(M\log^2 M)$。

code

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// 100/100
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
	cerr << "\e[1;33m" << s << " = [";
	while(l != r) {
		cerr << *l;
		cerr << (++l == r ? ']' : ',');
	}
	cerr << "\e[0m\n";
}

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-7;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

const int N = 1e5 + 25, LGN = 18;
vector<int> tmp_edge[N], edge[N];
int dep[N], arr[N], anc[LGN][N], in[N], out[N], t = 1;
ll pen[N];
struct fenwicktree {
	int arr[N << 1];
	void edt(int p, int v) {
		for(; p < (N << 1); p += p & -p)
			arr[p] += v;
	}
	int que(int p) {
		int res = 0;
		for(; p; p -= p & -p)
			res += arr[p];
		return res;
	}
} bit;
void build(int u, int lst) {
	if(arr[u]) {
		edge[lst].push_back(u);
		lst = u;
	}
	for(int v : tmp_edge[u])
		build(v, lst);
}
void dfs(int u) {
	in[u] = t++;
	for(int v : edge[u]) {
		dep[v] = dep[u] + 1;
		anc[0][v] = u;
		dfs(v);
	}
	out[u] = t++;
}
void binary_build(int n) {
	for(int i = 1; i < LGN; i++)
		for(int j = 1; j <= n; j++)
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
}

int find_first(int u) {
	if(bit.que(in[u]) == 0)
		return 0;
	for(int i = LGN - 1; ~i; i--) {
		int p = anc[i][u];
		if(p && bit.que(in[p]) == bit.que(in[u]))
			u = p;
	}
	return u;
}
void add(int u) {
	bit.edt(in[u], 1);
	bit.edt(out[u], -1);
}
void rem(int u) {
	bit.edt(in[u], -1);
	bit.edt(out[u], 1);
}

ll res = 0;
ll cur[N];
void edt(int p, ll v) {
	res -= cur[p];
	cur[p] = v;
	res += cur[p];
}

signed main() {
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 2, p; i <= n; i++)
		cin >> p, tmp_edge[p].push_back(i);

	vector<pair<int, int>> owo;
	for(int i = 0; i < m; i++) {
		int u, d, w;
		cin >> u >> d >> w;
		arr[u] = w;
		owo.push_back({d, u});
	}
	build(1, 1);

	dep[1] = 1;
	dfs(1);
	binary_build(n);
	sort(owo.begin(), owo.end(), [&](auto a, auto b) { return a.first == b.first ? dep[a.second] > dep[b.second] : a.first < b.first; });
	for(const auto &[d, u] : owo) {
		int p = u;
		ll cur_pen = arr[u];
		while(true) {
			p = find_first(p);
			if(!p)
				break;
			if(arr[p] - pen[p] - cur_pen <= 0) {
				rem(p);
				edt(p, 0);
				cur_pen += pen[p] - arr[p];
			}
			else {
				pen[p] += cur_pen;
				edt(p, arr[p] - pen[p]);
				break;
			}
		}
		edt(u, arr[u]);
		add(u);
	}

	cout << res << '\n';
}

O(M^2)

順便貼個 $\mathcal{O}(M^2)$ 的作法。

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// 19/100
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
	cerr << "\e[1;33m" << s << " = [";
	while(l != r) {
		cerr << *l;
		cerr << (++l == r ? ']' : ',');
	}
	cerr << "\e[0m\n";
}

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-7;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

const int N = 1e5 + 25, LGN = 18;
vector<int> tmp_edge[N], edge[N];
int dep[N], arr[N], anc[LGN][N], in[N], out[N], t;
ll pen[N];
struct segtree {
	ll arr[N << 1];
	int n;
	void init(int _n) { n = _n; }
	void edt(int p, int v) {
		for(arr[p += n] = v; p > 1; p >>= 1)
			arr[p >> 1] = arr[p] + arr[p ^ 1];
	}
	ll que(int l, int r) {
		ll res = 0;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				res += arr[l++];
			if(r & 1)
				res += arr[--r];
		}
		return res;
	}
};
void build(int u, int lst) {
	if(arr[u]) {
		edge[lst].push_back(u);
		lst = u;
	}
	for(int v : tmp_edge[u])
		build(v, lst);
}
void dfs(int u) {
	in[u] = t++;
	for(int v : edge[u]) {
		dep[v] = dep[u] + 1;
		anc[0][v] = u;
		dfs(v);
	}
	out[u] = t++;
}
void binary_build(int n) {
	for(int i = 1; i < LGN; i++)
		for(int j = 1; j <= n; j++)
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
}

// O(N^2) now
bool is[N];
int find_first(int u) {
	while(u && !is[u])
		u = anc[0][u];
	return u;
}
void add(int u) {
	is[u] = true;
}
void rem(int u) {
	is[u] = false;
}

ll res = 0;
ll cur[N];
void edt(int p, ll v) {
	res -= cur[p];
	cur[p] = v;
	res += cur[p];
}

signed main() {
	int n, m, k;
	cin >> n >> m >> k;
	assert(m <= 1000);
	for(int i = 2, p; i <= n; i++)
		cin >> p, tmp_edge[p].push_back(i);

	vector<pair<int, int>> owo;
	for(int i = 0; i < m; i++) {
		int u, d, w;
		cin >> u >> d >> w;
		arr[u] = w;
		owo.push_back({d, u});
	}
	build(1, 1);

	dep[1] = 1;
	dfs(1);
	binary_build(n);
	sort(owo.begin(), owo.end(), [&](auto a, auto b) { return a.first == b.first ? dep[a.second] > dep[b.second] : a.first < b.first; });
	for(const auto &[d, u] : owo) {
		int p = u;
		ll cur_pen = arr[u];
		while(true) {
			p = find_first(p);
			if(!p)
				break;
			if(arr[p] - pen[p] - cur_pen <= 0) {
				rem(p);
				edt(p, 0);
				cur_pen += pen[p] - arr[p];
			}
			else {
				pen[p] += cur_pen;
				edt(p, arr[p] - pen[p]);
				break;
			}
		}
		edt(u, arr[u]);
		add(u);
	}
	cout << res << '\n';
}