QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#824642	#3266. 摧毁“树状图”	UKE_Automation	100 ✓	65ms	9792kb	C++14	2.6kb	2024-12-21 15:04:07	2024-12-21 15:04:12

Judging History

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

[2024-12-21 15:04:12]
评测

测评结果：100
用时：65ms
内存：9792kb

查看

[2024-12-21 15:04:07]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 2e5 + 5;
const int Inf = 2e9;

int T, Id;
int n;
int head[Maxn], edgenum;
struct node {
	int nxt, to;
}edge[Maxn];

void add(int u, int v) {
	edge[++edgenum] = {head[u], v};
	head[u] = edgenum;
}

int dp[Maxn][4], siz[Maxn];
int ans = 0;
void dfs(int x, int fth) {
	siz[x] = 0;
	for(int i = head[x]; i; i = edge[i].nxt) {
		int to = edge[i].to;
		if(to == fth) continue;
		dfs(to, x);
		siz[x]++;
	}
	dp[x][0] = dp[x][1] = dp[x][3] = siz[x] + 1 - (x == 1);
	dp[x][2] = 1;
	int mx1 = 1, mx2 = 1, mx3 = 1, mx0 = 1, lmx0 = 1;
	for(int i = head[x]; i; i = edge[i].nxt) {
		int to = edge[i].to;
		if(to == fth) continue;
		ans = max(ans, dp[x][3] + dp[to][0] - 2);
		ans = max(ans, mx3 + dp[to][0] + siz[x] - 3 - (x == 1) + (mx3 == 1));
		ans = max(ans, mx0 + dp[to][3] + siz[x] - 3 - (x == 1) + (mx0 == 1));
		ans = max(ans, max(mx1, mx2) + max(dp[to][1], dp[to][2]) - 1);
		ans = max(ans, dp[x][1] + dp[to][1] - 2);
		ans = max(ans, dp[x][1] + dp[to][2] - 1);
		dp[x][0] = max(dp[x][0], dp[to][0] + siz[x] - 1 - (x == 1));
		dp[x][1] = max(dp[x][1], mx0 + dp[to][0] + siz[x] - 3 - (x == 1) + (mx0 == 0));
		dp[x][2] = max(dp[x][2], max({dp[to][0], dp[to][2], dp[to][1]}));
		dp[x][3] = max(dp[x][3], mx0 + lmx0 + dp[to][0] + siz[x] - 5 - (x == 1) + (mx0 == 1) + (lmx0 == 1));
		dp[x][3] = max(dp[x][3], mx1 + dp[to][0] + siz[x] - 3 - (x == 1) + (mx1 == 1));
		dp[x][3] = max(dp[x][3], mx2 + dp[to][0] + siz[x] - 2 - (x == 1));
		dp[x][3] = max(dp[x][3], mx0 + dp[to][1] + siz[x] - 3 - (x == 1) + (mx0 == 1));
		dp[x][3] = max(dp[x][3], mx0 + dp[to][2] + siz[x] - 2 - (x == 1) + (mx0 == 1));
		dp[x][3] = max(dp[x][3], dp[to][3] + siz[x] - 1 - (x == 1));
		ans = max({ans, dp[x][0], dp[x][1], dp[x][2], dp[x][3]});
		mx1 = max(dp[to][1], mx1);
		mx2 = max(dp[to][2], mx2);
		mx3 = max(dp[to][3], mx3);
		if(dp[to][0] > mx0) {
			lmx0 = mx0;
			mx0 = dp[to][0];
		}
		else if(dp[to][0] > lmx0) {
			lmx0 = dp[to][0];
		}
	}
	dp[x][1] = max(dp[x][1], dp[x][0]);
//	cout << x << " " << dp[x][0] << " " << dp[x][1] << " " << dp[x][2] << " " << dp[x][3] << '\n';
}

void init() {
	ans = edgenum = 0;
	for(int i = 1; i <= n; i++) head[i] = 0;
}

void solve() {
	init();
	cin >> n;
	if(Id == 1) {
		int a; cin >> a; cin >> a;
	}
	if(Id == 2) {
		int a; cin >> a; cin >> a; cin >> a; cin >> a;
	}
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(1, 0);
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> Id;
	while(T--) solve();
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 4

Accepted

time: 0ms

memory: 5684kb

input:

output:

result:

ok 100 lines

Test #2:

score: 4

Accepted

time: 1ms

memory: 5612kb

input:

output:

result:

ok 100 lines

Test #3:

score: 4

Accepted

time: 1ms

memory: 5764kb

input:

output:

result:

ok 100 lines

Test #4:

score: 4

Accepted

time: 1ms

memory: 7656kb

input:

output:

result:

ok 100 lines

Test #5:

score: 4

Accepted

time: 1ms

memory: 7748kb

input:

output:

result:

ok 1000 lines

Test #6:

score: 4

Accepted

time: 1ms

memory: 7788kb

input:

output:

result:

ok 1000 lines

Test #7:

score: 4

Accepted

time: 0ms

memory: 5612kb

input:

output:

result:

ok 10000 lines

Test #8:

score: 4

Accepted

time: 1ms

memory: 5700kb

input:

148 2
4 2 2 1 1
1 2
1 3
2 4
81 31 27 40 39
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
2...

output:

result:

ok 148 lines

Test #9:

score: 4

Accepted

time: 1ms

memory: 7664kb

input:

output:

result:

ok 130 lines

Test #10:

score: 4

Accepted

time: 0ms

memory: 7680kb

input:

output:

result:

ok 124 lines

Test #11:

score: 4

Accepted

time: 1ms

memory: 7704kb

input:

123 2
57 50 57 21 11
23 28
31 20
54 53
44 47
25 51
54 22
2 7
29 15
31 1
51 9
16 49
22 50
55 43
38 5
23 10
11 27
45 26
54 34
52 45
34 56
19 42
35 25
8 54
8 40
44 38
46 31
40 46
32 4
54 36
31 24
40 44
11 52
54 32
50 12
35 13
6 18
50 6
57 48
4 16
8 3
17 14
18 30
22 39
21 17
16 21
57 33
54 35
13 37
2 55...

output:

result:

ok 123 lines

Test #12:

score: 4

Accepted

time: 1ms

memory: 5632kb

input:

output:

result:

ok 124 lines

Test #13:

score: 4

Accepted

time: 1ms

memory: 7740kb

input:

output:

result:

ok 122 lines

Test #14:

score: 4

Accepted

time: 3ms

memory: 9780kb

input:

102 2
746 372 319 255 223
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
...

output:

result:

ok 102 lines

Test #15:

score: 4

Accepted

time: 0ms

memory: 5728kb

input:

output:

result:

ok 97 lines

Test #16:

score: 4

Accepted

time: 0ms

memory: 7744kb

input:

output:

result:

ok 132 lines

Test #17:

score: 4

Accepted

time: 0ms

memory: 7704kb

input:

95 2
2 1 1 1 1
2 1
2 1 1 1 1
2 1
276 200 134 148 227
110 240
266 142
222 199
223 182
186 126
101 100
144 184
151 40
251 158
4 260
115 48
101 118
189 32
110 20
171 22
9 128
182 156
30 52
177 241
37 257
229 19
26 262
26 259
140 253
251 143
78 148
118 47
118 146
103 53
186 217
208 65
177 45
203 90
242 ...

output:

result:

ok 95 lines

Test #18:

score: 4

Accepted

time: 3ms

memory: 9780kb

input:

output:

result:

ok 139 lines

Test #19:

score: 4

Accepted

time: 0ms

memory: 9792kb

input:

output:

result:

ok 87 lines

Test #20:

score: 4

Accepted

time: 50ms

memory: 8176kb

input:

64 2
20240 10119 6143 8191 7167
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
...

output:

result:

ok 64 lines

Test #21:

score: 4

Accepted

time: 50ms

memory: 8080kb

input:

53 1
14943 6143 5119
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52...

output:

result:

ok 53 lines

Test #22:

score: 4

Accepted

time: 50ms

memory: 7960kb

input:

output:

result:

ok 73 lines

Test #23:

score: 4

Accepted

time: 57ms

memory: 8308kb

input:

83 2
459 361 416 176 188
22 354
229 318
170 243
104 438
255 366
169 92
85 328
401 110
108 317
59 162
122 456
415 51
277 396
231 91
328 218
267 375
80 182
348 312
34 165
311 226
107 96
203 416
35 33
91 89
130 392
335 20
188 57
66 108
345 391
251 194
195 246
73 98
345 353
229 231
41 422
218 180
187 42...

output:

result:

ok 83 lines

Test #24:

score: 4

Accepted

time: 65ms

memory: 7896kb

input:

78 1
303 138 167
132 83
218 96
219 186
188 201
290 286
126 16
117 14
45 74
24 158
20 77
155 273
84 208
168 194
161 72
103 234
167 270
170 132
141 173
227 242
75 15
82 244
235 35
88 166
20 38
50 282
137 280
3 168
105 42
116 134
276 197
276 33
126 55
218 267
20 84
98 76
86 37
227 288
288 73
220 188
81...

output:

result:

ok 78 lines

Test #25:

score: 4

Accepted

time: 60ms

memory: 8260kb

input:

output:

result:

ok 96 lines