QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129534#5418. Color the TreelhzawaWA 29ms13520kbC++142.7kb2023-07-22 20:26:022023-07-22 20:26:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-22 20:26:05]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:13520kb
  • [2023-07-22 20:26:02]
  • 提交

answer

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: E. Color the Tree
// Contest: Codeforces - The 2022 ICPC Asia Nanjing Regional Contest
// URL: https://codeforces.com/gym/104128/problem/E
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 18;
vector<int> G[N], D[N];
int f[N][M];
int dep[N];
void dfs_dep(int u) {
	for (int i = 1; i < M; i++) {
		f[u][i] = f[f[u][i - 1]][i - 1];
	}
	D[dep[u]].push_back(u);
	for (int v : G[u]) {
		if (v == f[u][0]) {
			continue;
		}
		f[v][0] = u, dep[v] = dep[u] + 1, dfs_dep(v);
	}
	return ;
}
int LCA(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int i = 0, dc = dep[u] - dep[v]; i < M; i++) {
		if ((dc >> i) & 1) {
			u = f[u][i];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = M - 1; ~ i; i--) {
		if (f[u][i] != f[v][i]) {
			u = f[u][i], v = f[v][i];
		}
	}
	return f[u][0];
}
vector<int> vG[N];
long long mn[N][M];
long long query(int l, int r) {
	int k = __lg(r - l + 1);
	return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
long long dfs_f(int u, int fa, int d) {
	long long res = LLONG_MAX;
	if (dep[u] == d);
	else {
		res = 0;
		for (int v : vG[u]) {
			res += dfs_f(v, u, d);
		}
	}
	return min(res, query(d - dep[u], d - (dep[fa] + 1)));
}
int stk[N], top;
long long calc(int d) {
	top = stk[1] = 1, vG[1].clear();
	for (int u : D[d]) {
		vG[u].clear();
		int l = LCA(u, stk[top]);
		if (l == stk[top]) {
			stk[++top] = u;
			continue;
		}
		for (; dep[l] < dep[stk[top - 1]]; top--) {
			vG[stk[top - 1]].push_back(stk[top]);
		}
		if (l == stk[top - 1]) {
			vG[l].push_back(stk[top]), top--;
		}
		else {
			vG[l].clear(), vG[l].push_back(stk[top]), stk[top] = l;
		}
		stk[++top] = u;
	}
	for (; top > 1; top--) {
		vG[stk[top - 1]].push_back(stk[top]);
	}
	return dfs_f(1, 0, d);
}
void solve() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &mn[0][i]);	
	}
	for (int i = 1; (1 << i) <= n; i++) {
		for (int l = 0, r = (1 << i) - 1; r < n; l++, r++) {
			mn[i][l] = min(mn[i - 1][l], mn[i - 1][l + (1 << (i - 1))]);
		}
	}
	for (int i = 1; i <= n; i++) {
		G[i].clear();
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		G[x].push_back(y), G[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		D[i].clear();	
	}
	dep[1] = 1;
	dfs_dep(1);
	long long ans = mn[0][0];
	for (int i = 2; i <= n && ! D[i].empty(); i++) {
		ans += calc(i);
	}
	printf("%lld\n", ans);
	return ;
}
int main() {
	int _;
	scanf("%d", &_);
	for (; _; _--) {
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 13520kb

input:

3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4

output:

35
17
1218

result:

ok 3 number(s): "35 17 1218"

Test #2:

score: 0
Accepted
time: 29ms
memory: 12732kb

input:

3000
54
43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44
1 2
1 3
2 4
3 5
4 6
2 7
4 8
1 9
3 10
1 11
8 12
2 13
9 14
1 15
1 16
15 17
15 18
7 19
1 20
19 21
13 22
10 23
17 24
9 25
9 26
24 27
8 28...

output:

180
168
222
230
156
240
225
126
100
81
155
73
154
127
149
124
228
230
132
187
153
170
78
282
195
286
191
211
119
197
211
233
88
252
239
233
173
180
195
121
109
148
180
175
226
210
182
97
199
59
56
31
115
204
203
172
139
208
53
140
189
170
173
137
233
94
163
273
80
350
156
133
146
159
240
269
137
222...

result:

ok 3000 numbers

Test #3:

score: -100
Wrong Answer
time: 29ms
memory: 13328kb

input:

300
474
5 24 21 41 15 23 43 48 32 19 27 40 10 49 40 6 18 41 43 31 45 18 35 36 12 10 23 45 28 23 14 43 37 45 12 16 20 17 49 13 22 8 30 19 27 40 22 14 30 47 16 39 25 48 21 26 50 8 14 26 9 30 41 15 44 24 16 46 50 39 25 47 24 45 21 18 26 21 5 39 15 10 47 48 11 44 44 33 23 14 35 39 35 30 38 9 13 15 39 5 ...

output:

329
183
264
219
323
220
348
342
410
395
80
201
299
144
207
408
360
215
283
104
320
394
277
210
273
285
242
253
265
379
360
322
202
351
195
196
266
270
171
342
239
283
286
300
331
317
345
268
173
296
275
224
480
330
264
162
199
378
254
214
231
293
229
259
241
268
380
419
233
185
364
341
328
237
320
3...

result:

wrong answer 150th numbers differ - expected: '446', found: '464'