UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202980#3525. 车窗外 这夜色 流光溢彩cqzxz1004329ms122848kbC++112.5kb2024-02-18 10:09:262024-02-18 12:31:22

answer

#include<bits/stdc++.h>
#define int long long
#define il inline
namespace things{
	il int rd(){
		int f = 1, x = 0;
		char ch = getchar();
		while(ch < '0' || ch > '9'){
			if (ch == '-' ) f = -1;
			ch = getchar();
		}
		while(ch >= '0' && ch <= '9'){
			x = x * 10 + ch - '0';
			ch = getchar();
		}
		return x * f;
	}
	il int max(int x, int y){
		return std::max(x, y);
	}
	il int min(int a, int b){
		return std::min(a, b);
	}
}
using namespace things;
using namespace std;

const int N = 1e6 + 5;
int v[N << 1], nxt[N << 1], head[N];
int w[N << 1];
int n, m, tot, cur;
bool key[N];
int dfn[N], seq[N], st[N];
int s[N], f[N], dist[N];

void add(int x, int y){
	v[++tot] = y; w[tot] = 1; nxt[tot] = head[x]; head[x] = tot;
}

struct Sgt{
	int mx[N << 2], tag[N << 2];
	void update(int o){
		mx[o] = max(mx[o << 1], mx[o << 1 | 1]);
	}
	void pushdown(int o){
		if (tag[o]){
			mx[o << 1] += tag[o];
			mx[o << 1 | 1] += tag[o];
			tag[o << 1] += tag[o];
			tag[o << 1 | 1] += tag[o];
			tag[o] = 0;
		}
	}
	void build(int o, int l, int r){
		if (l == r){
			mx[o] = dist[seq[l]];
			return;
		}
		int mid = (l + r) >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		update(o);
	}
	void add(int o, int lb, int rb, int l, int r, int d){
		if (l > rb || r < lb) return;
		if (l <= lb && r >= rb){
			mx[o] += d;
			tag[o] += d;
			return;
		}
		pushdown(o);
		int mid = (lb + rb) >> 1;
		add(o << 1, lb, mid, l, r, d);
		add(o << 1 | 1, mid + 1, rb, l, r, d);
		update(o);
	}
	void add(int l, int r, int d){
		if (l <= r) add(1, 1, m, l, r, d);
	}
	int query(int o, int lb, int rb, int l, int r){
		if (l > rb || r < lb) return 0;
		if (l <= lb && r >= rb) return mx[o];
		pushdown(o);
		int mid = (lb + rb) >> 1;
		return max(query(o << 1, lb, mid, l, r), query(o << 1 | 1, mid + 1, rb, l, r));
	}
}sgt;

void dfs(int x, int fa){
	if (key[x]){
		s[x] = 1;
		dfn[x] = ++cur;
		seq[cur] = x;
	}
	for (int i = head[x]; i; i = nxt[i]){
		if (v[i] != fa){
			dist[v[i]] = dist[x] + w[i];
			dfs(v[i], x);
			s[x] += s[v[i]];
			if (s[v[i]]) f[x] += f[v[i]] + 2ll * w[i];
		}
	}
	if (s[x]) st[x] = cur - s[x] + 1;
}

signed main(){
	n = rd(), m = rd();
	for (int i = 1; i <= m; i++){
		int x;
		x = rd();
		key[x] = 1;
	}
	for (int i = 1; i <= n - 1; i++){
		int x, y;
		x = rd(), y = rd();
		add(x, y);
		add(y, x);
	}
	dfs(1, 0);
	sgt.build(1, 1, m);
	cout << f[1] - sgt.query(1, 1, m, 1, m);
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1208kb

input:

9 10
9 5 4 8 2 3 7 1 6 0
2 9
8 9
5 8
6 2
1 9
3 8
4 8
7 5

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

8 3
3 6 8
2 1
3 1
7 3
6 7
4 7
5 3
8 7

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

7 4
4 2 3 5
2 7
3 7
5 2
6 5
1 6
4 7

output:

7

result:

ok 1 number(s): "7"

Test #4:

score: 0
Accepted
time: 1ms
memory: 1204kb

input:

10 2
4 8
6 9
5 6
4 9
3 6
7 6
8 6
10 6
2 5
1 7

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

9 8
9 2 5 4 1 8 3 7
8 5
4 5
6 4
7 6
3 6
9 5
1 7
2 5

output:

11

result:

ok 1 number(s): "11"

Test #6:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

5 9
4 2 3 5 1 0 0 0 0
5 4
2 4
1 5
3 5

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

10 6
8 6 4 3 9 7
5 2
9 5
4 9
10 9
1 10
7 2
3 1
8 3
6 8

output:

13

result:

ok 1 number(s): "13"

Test #8:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

6 8
4 3 6 2 5 1 0 0
6 2
5 2
1 6
3 6
4 1

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: 0
Accepted
time: 0ms
memory: 1208kb

input:

10 9
5 10 2 3 4 7 1 6 9
7 3
10 3
9 7
8 3
1 3
2 9
6 10
4 7
5 4

output:

12

result:

ok 1 number(s): "12"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1208kb

input:

10 8
3 8 7 6 10 5 1 4
4 5
10 4
8 10
1 10
9 5
7 5
6 10
2 4
3 6

output:

10

result:

ok 1 number(s): "10"

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 0ms
memory: 1700kb

input:

4996 15
3964 3029 1403 4476 2880 3132 2415 1901 4817 3331 1232 1414 2254 401 2545
4250 1566
821 1566...

output:

855

result:

ok 1 number(s): "855"

Test #12:

score: 0
Accepted
time: 0ms
memory: 1692kb

input:

4997 512
4033 651 4512 646 2737 377 1672 4149 3949 776 3966 241 1677 4612 1028 2485 2449 1618 1852 4...

output:

2569

result:

ok 1 number(s): "2569"

Test #13:

score: 0
Accepted
time: 0ms
memory: 1716kb

input:

5000 960
800 4614 587 2573 4864 2880 611 3419 702 2067 1616 2539 2826 599 205 2388 2876 3768 4698 25...

output:

4994

result:

ok 1 number(s): "4994"

Test #14:

score: 0
Accepted
time: 1ms
memory: 1692kb

input:

4996 196
3368 4332 2571 1682 1827 1941 3598 3164 289 2166 2999 3388 4456 3036 1447 3979 1942 3820 23...

output:

1277

result:

ok 1 number(s): "1277"

Test #15:

score: 0
Accepted
time: 2ms
memory: 1756kb

input:

4997 1670
2081 2936 2340 3478 4319 206 3890 2022 852 4974 2512 4642 4487 391 2335 1005 2053 4929 209...

output:

5942

result:

ok 1 number(s): "5942"

Test #16:

score: 0
Accepted
time: 0ms
memory: 1848kb

input:

4996 4532
4599 770 1111 3946 4537 57 2671 4342 2118 4091 2427 1021 3940 875 251 1722 1633 550 3087 3...

output:

9521

result:

ok 1 number(s): "9521"

Test #17:

score: 0
Accepted
time: 0ms
memory: 1788kb

input:

4998 3253
279 2476 4104 1766 1416 274 2471 4442 308 1610 3800 1338 4646 1099 1743 1492 1776 4448 241...

output:

8046

result:

ok 1 number(s): "8046"

Test #18:

score: 0
Accepted
time: 0ms
memory: 1704kb

input:

5000 683
509 898 2709 3838 1922 2803 107 3007 536 660 284 2343 997 4928 4449 4417 3420 604 2 638 197...

output:

3135

result:

ok 1 number(s): "3135"

Test #19:

score: 0
Accepted
time: 0ms
memory: 1872kb

input:

4998 4406
4756 3228 4083 2427 543 912 2483 298 2229 2963 2024 4530 3998 4701 1288 4081 1981 2776 245...

output:

8695

result:

ok 1 number(s): "8695"

Test #20:

score: 0
Accepted
time: 0ms
memory: 1780kb

input:

4996 4041
3262 4271 2855 234 2106 3362 470 2826 3891 2705 3533 1645 1871 2807 4339 1370 303 47 601 4...

output:

8938

result:

ok 1 number(s): "8938"

Subtask #3:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 335ms
memory: 90400kb

input:

999997 1
609695
738478 594839
317328 594839
201435 594839
580977 594839
440742 738478
304787 580977
...

output:

40593

result:

ok 1 number(s): "40593"

Test #22:

score: 0
Accepted
time: 417ms
memory: 71684kb

input:

1000000 1
952552
243709 679245
653887 679245
609827 679245
681973 679245
34205 681973
951892 34205
2...

output:

24

result:

ok 1 number(s): "24"

Test #23:

score: 0
Accepted
time: 315ms
memory: 92048kb

input:

999995 1
217420
630267 364824
720204 364824
871920 720204
870371 720204
625951 364824
163720 364824
...

output:

97003

result:

ok 1 number(s): "97003"

Test #24:

score: 0
Accepted
time: 402ms
memory: 71684kb

input:

999996 1
389900
940443 191238
140630 191238
63551 940443
985771 140630
778819 985771
448938 191238
3...

output:

24

result:

ok 1 number(s): "24"

Test #25:

score: 0
Accepted
time: 331ms
memory: 92704kb

input:

999996 1
514095
869056 600885
844857 600885
909976 844857
671491 909976
651232 671491
548725 651232
...

output:

57631

result:

ok 1 number(s): "57631"

Subtask #4:

score: 50
Accepted

Test #26:

score: 50
Accepted
time: 511ms
memory: 116688kb

input:

999996 563443
695404 211314 551983 316474 937862 38389 747185 3258 737288 354968 158575 571013 63181...

output:

1480363

result:

ok 1 number(s): "1480363"

Test #27:

score: 0
Accepted
time: 495ms
memory: 122848kb

input:

1000000 745426
558698 478713 172317 999443 332691 877210 37327 431001 666697 739190 500934 440505 56...

output:

1650442

result:

ok 1 number(s): "1650442"

Test #28:

score: 0
Accepted
time: 541ms
memory: 117580kb

input:

999995 678416
587427 520855 825924 996298 759521 359824 827243 699190 523039 475401 472819 873193 59...

output:

1636865

result:

ok 1 number(s): "1636865"

Test #29:

score: 0
Accepted
time: 389ms
memory: 111320kb

input:

999996 365402
530718 946843 136010 419613 401117 590144 570477 859767 409307 359647 138508 32732 818...

output:

1251915

result:

ok 1 number(s): "1251915"

Test #30:

score: 0
Accepted
time: 589ms
memory: 118704kb

input:

999995 822057
312794 128807 350384 546108 796929 79650 85378 695458 499809 259281 485039 528948 8083...

output:

1810476

result:

ok 1 number(s): "1810476"

Extra Test:

score: 0
Extra Test Passed