ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203309 | #3557. 平衡树 | wosile | 100 | 1954ms | 28612kb | C++11 | 1.0kb | 2024-02-22 10:34:45 | 2024-02-22 13:06:07 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,Q;
vector<int>T[200005];
int U[200005],V[200005];
int dfn[200005],dfr[200005],tot=0;
void dfs(int x,int fa){
dfn[x]=dfr[x]=++tot;
for(int v:T[x])if(v!=fa){
dfs(v,x);
dfr[x]=dfr[v];
}
}
int p[200005],c[200005];
int query(int x){
int sum=0;
for(;x;x-=(x&-x))sum+=c[x];
return sum;
}
int main(){
scanf("%d%d",&n,&Q);
for(int i=1;i<n;i++){
scanf("%d%d",&U[i],&V[i]);
T[U[i]].push_back(V[i]);
T[V[i]].push_back(U[i]);
}
dfs(1,0);
for(int i=1;i<n;i++)if(dfn[U[i]]>dfn[V[i]])swap(U[i],V[i]);
while(Q--){
int len,S,cnt=0;
scanf("%d",&len);
for(int i=1;i<=len;i++){
scanf("%d",&p[i]);
p[i]=V[p[i]];
}
for(int i=1;i<=len;i++)for(int j=dfn[p[i]];j<=n;j+=(j&-j))c[j]++;
for(int i=1;i<=len;i++){
int d=query(dfr[p[i]])-query(dfn[p[i]]-1);
if(d==1)++cnt;
if(d==len)++cnt;
}
scanf("%d",&S);
printf("%d\n",S-S/cnt*2);
for(int i=1;i<=len;i++)for(int j=dfn[p[i]];j<=n;j+=(j&-j))c[j]--;
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 5944kb
input:
5 2 3 2 2 4 4 1 1 5 3 1 3 4 6 2 2 4 5
output:
0 1
result:
ok 2 lines
Test #2:
score: 5
Accepted
time: 0ms
memory: 5948kb
input:
5 2 3 2 4 2 2 1 1 5 4 1 2 3 4 8 1 3 7
output:
4 1
result:
ok 2 lines
Test #3:
score: 5
Accepted
time: 0ms
memory: 6052kb
input:
2000 123 5 1633 10 46 11 1976 13 510 16 901 17 837 18 1845 19 745 25 1905 26 258 29 836 30 1198 31 2...
output:
2518 2972 5118 3616 4311 622 1 1 30 7414 1481 3969 1 4227 4190 2377 1272 1566 0 7355 5564 4181 1730 ...
result:
ok 123 lines
Test #4:
score: 5
Accepted
time: 3ms
memory: 6040kb
input:
2000 154 3 1439 4 1463 8 657 12 449 13 1287 18 1067 24 1928 30 1909 31 172 33 370 36 104 37 1224 38 ...
output:
5420 5537 2309 5771 503 3077 1049 2518 1532 1202 1091 0 5173 7540 3174 3042 1067 3737 1443 5194 7374...
result:
ok 154 lines
Test #5:
score: 5
Accepted
time: 2ms
memory: 6048kb
input:
2000 149 1 1989 4 1751 5 1067 6 29 13 1388 14 930 15 473 19 1640 21 1425 28 70 29 1970 30 149 31 722...
output:
5084 433 7962 5703 0 214 0 1 7541 3121 91 1540 5101 32 0 1 1674 1456 3100 173 4953 2286 2019 5640 39...
result:
ok 149 lines
Test #6:
score: 5
Accepted
time: 0ms
memory: 6048kb
input:
2000 76 2 666 7 1415 8 468 9 375 13 1051 15 433 17 567 20 583 29 1255 30 651 31 475 34 1528 38 1249 ...
output:
2584 2945 3540 819 5317 1890 7019 0 1596 919 6476 8336 5479 1843 0 856 7840 6429 3746 4726 0 2527 16...
result:
ok 76 lines
Test #7:
score: 5
Accepted
time: 90ms
memory: 28612kb
input:
200000 817 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 1...
output:
1 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 0 0 ...
result:
ok 817 lines
Test #8:
score: 5
Accepted
time: 85ms
memory: 28608kb
input:
200000 761 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 1...
output:
1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 ...
result:
ok 761 lines
Test #9:
score: 5
Accepted
time: 154ms
memory: 16224kb
input:
200000 80031 2 56605 5 189458 10 52573 16 40609 20 147707 21 51606 25 85354 26 80273 28 146532 30 30...
output:
1 1 84592587 282777332 17448421 224692442 200184146 0 0 0 0 1 142630100 0 279438899 1 0 196329433 25...
result:
ok 80031 lines
Test #10:
score: 5
Accepted
time: 163ms
memory: 16204kb
input:
200000 80110 5 94780 7 25504 8 121345 10 55001 11 80845 15 75079 19 110524 20 24218 21 106900 33 474...
output:
125396798 287042965 1 1 0 266980734 227570895 276708838 235412257 193522402 290542021 92010025 1 154...
result:
ok 80110 lines
Test #11:
score: 5
Accepted
time: 172ms
memory: 16200kb
input:
200000 79935 2 73053 3 62426 5 10346 6 57113 9 161123 11 99199 13 33136 17 155443 18 39834 19 164439...
output:
209963314 168206964 83579270 7448413 0 0 2388804 66721195 144755864 166639227 5493227 0 280850279 18...
result:
ok 79935 lines
Test #12:
score: 5
Accepted
time: 163ms
memory: 16200kb
input:
200000 79994 2 35483 5 39827 12 56887 13 25533 15 153428 18 15164 19 11878 20 75339 24 119759 25 827...
output:
1 0 0 1 0 152209571 1 0 67846443 256867537 152510134 300997101 7831242 179751117 0 166369518 0 1 0 2...
result:
ok 79994 lines
Test #13:
score: 5
Accepted
time: 120ms
memory: 16628kb
input:
200000 10 1 18212 2 12539 6 113047 7 124259 11 181026 24 171770 26 106553 28 57953 31 167402 33 8548...
output:
465397042 593629129 798615913 424347866 321194689 757403436 468811817 227100827 255588579 815681185
result:
ok 10 lines
Test #14:
score: 5
Accepted
time: 127ms
memory: 16604kb
input:
200000 10 1 6332 3 82822 8 40816 9 82907 10 105786 12 44658 16 55833 23 38485 25 3392 26 88759 28 25...
output:
405675139 897537112 622929104 386104869 956720187 471636816 51478759 57111230 377734824 921982763
result:
ok 10 lines
Test #15:
score: 5
Accepted
time: 114ms
memory: 16596kb
input:
200000 10 2 159917 7 96456 8 37219 11 132388 15 34463 17 35571 21 315 22 67883 24 793 26 115757 28 8...
output:
453053254 185258202 909143733 615505893 541872704 788457111 758509860 663168261 581419346 206803769
result:
ok 10 lines
Test #16:
score: 5
Accepted
time: 144ms
memory: 16368kb
input:
200000 333 7 150698 8 45902 10 197132 12 46932 13 198593 14 42732 21 1877 22 188009 23 85556 25 1092...
output:
366312167 1819647 288818627 289251963 637379204 268258345 710678264 308430357 314485440 813323879 20...
result:
ok 333 lines
Test #17:
score: 5
Accepted
time: 154ms
memory: 16404kb
input:
200000 133 1 29089 4 118283 5 54192 6 124551 9 82454 11 16278 16 151949 18 51321 19 94155 26 145653 ...
output:
74490490 128961041 324286623 565693061 204610350 590648521 715421578 783927827 550419967 791296597 2...
result:
ok 133 lines
Test #18:
score: 5
Accepted
time: 160ms
memory: 16392kb
input:
200000 262 7 158500 12 144061 18 48427 20 77748 21 175177 22 121943 25 89477 29 3820 31 13537 37 301...
output:
325846007 445365531 265881246 901849563 408346699 574041293 314978805 300077023 58626797 365208812 6...
result:
ok 262 lines
Test #19:
score: 5
Accepted
time: 154ms
memory: 16448kb
input:
200000 212 4 5924 5 68470 6 34717 8 39714 11 23683 14 169146 15 34814 29 152118 33 46998 35 6733 39 ...
output:
87378768 897377073 292438843 214404930 363649283 255682178 962771228 120043816 74310682 438997094 98...
result:
ok 212 lines
Test #20:
score: 5
Accepted
time: 149ms
memory: 16428kb
input:
200000 214 1 29911 16 121241 20 36766 24 85712 25 150205 29 7071 30 187675 31 153914 36 124592 40 16...
output:
988959638 449591 606050087 103906883 365178401 804421442 400944302 851325297 502059046 544860612 589...
result:
ok 214 lines
Extra Test:
score: 0
Extra Test Passed