ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#202980 | #3525. 车窗外 这夜色 流光溢彩 | cqzxz | 100 | 4329ms | 122848kb | C++11 | 2.5kb | 2024-02-18 10:09:26 | 2024-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;
}
Details
小提示:点击横条可展开更详细的信息
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