ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203296 | #3557. 平衡树 | snow_trace | 100 | 4076ms | 48200kb | C++11 | 3.3kb | 2024-02-22 09:30:05 | 2024-02-22 13:03:52 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int dfn[200005];
vector<int>p[200005];
struct node{
int l,r,sum,lazy;
void add(int x){
if(x == 1)sum = r-l,lazy = 1;
if(x == -1)sum =0 ,lazy =-1;
}
}tree[1000005];
void push_up(int k){
tree[k].sum = tree[k<<1].sum+tree[k<<1|1].sum;
}void push_down(int k){
if(tree[k].lazy!=0){
tree[k<<1].add(tree[k].lazy),tree[k<<1|1].add(tree[k].lazy);tree[k].lazy = 0;
}
}void build(int l,int r,int k){
tree[k].l =l ,tree[k].r = r;
if(l+1 == r){
return;
}build(l,l+r>>1,k<<1),build(l+r>>1,r,k<<1|1);
}void update(int l,int r,int k,int add){
int ll = tree[k].l,rr = tree[k].r;
if(l>=rr or ll>=r)return;
if(l<=ll and rr<=r){
tree[k].add(add);return;
}push_down(k);
update(l,r,k<<1,add),update(l,r,k<<1|1,add);
push_up(k);
}int query(int l,int r,int k){
int ll= tree[k].l,rr = tree[k].r;
if(l>=rr or ll>=r)return 0;
if(l<=ll and rr<=r)return tree[k].sum;
push_down(k);
return query(l,r,k<<1)+query(l,r,k<<1|1);
}
int x[200005],y[200005],fa[200005],dep[200005],sz[200005];int nw=0;
void dfs1(int now,int f){
fa[now] = f;dep[now] = dep[f]+1;dfn[now] = ++nw;sz[now] = 1;
for(int i =0;i<p[now].size();i++){
if(p[now][i] == f)continue;dfs1(p[now][i],now);sz[now]+=sz[p[now][i]];
}return;
}int k,s;
int a[200005],tt[200005];
bool cmp(int a,int b){
return dep[a]<dep[b];
}
#define lowbit(x) x&(-x)
int Tree[200005];
void upd(int pos,int add){
for(int i = pos;i<=n;i+=lowbit(i))Tree[i]+=add;
}int qquery(int pos){
int res =0;for(int i = pos;i>0;i-=lowbit(i))res+=Tree[i];return res;
}
void solve(){
cin >> k;
for(int i = 1;i<=k;i++){
int aa;cin >> aa;
if(dep[x[aa]]>dep[y[aa]])a[i] = x[aa];else a[i] = y[aa];
}sort(a+1,a+1+k,cmp);cin>> s;
update(1,n+1,1,-1);
vector<int>pf,ps;
// for(int i = 1;i<=k;i++){
// if(query(dfn[a[i]],dfn[a[i]]+sz[a[i]],1) == 0){
// pf.push_back(a[i]);
// update(dfn[a[i]],dfn[a[i]]+sz[a[i]],1,1);
// }
// }
update(1,n+1,1,-1);
// for(int i= 1;i<=n;i++)cout<< query(i,i+1,1) << " ";cout << endl;
for(int i =k;i>=1;i--){
if(query(dfn[a[i]],dfn[a[i]]+sz[a[i]],1) == 0){
ps.push_back(a[i]);
update(dfn[a[i]],dfn[a[i]]+sz[a[i]],1,1);upd(dfn[a[i]],1);
}
}int l = 0,r = s;int mxx =0 ;
for(int i = 1;i<=k;i++)mxx = max(mxx,qquery(dfn[a[i]]+sz[a[i]]-1)-qquery(dfn[a[i]]-1));
for(int x:ps)upd(dfn[x],-1);
//cout << mxx << " " << ps.size() << endl;
while(l<r){
// cout << 111 << endl;
int mid = l+r>>1;
/*
x-(n-x)<=s
2x-n<=s
x<=(n+s)/2
(n-x)-x<=s
n-2x<=s
2x>=n-s
x>=(n-s)/2
*/
int mn = (s-mid+1)/2,mx = (s+mid)/2;
// cout << " " << s << " " << mid << " " << mn << " " << mx << endl;
if(mn*mxx>mx or mn*ps.size()>s)l = mid+1;
else r = mid;
}cout << r << '\n';
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>> n >> q;
for(int i = 1;i<n;i++){
int a,b;cin >> a >> b;
x[i] = a,y[i] =b;p[a].push_back(b),p[b].push_back(a);
}dfs1(1,1);build(1,n+1,1);
while(q--){
solve();
}
return 0;
}
/*
建虚树然后二分答案。
不想建虚树怎么办?
其实只需要先把极端的点都预处理出来。
先预处理出叶子节点
我们考虑让子树的size在满足条件的情况下尽可能的小
然后把多余的点全部丢给1
*/
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 5988kb
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: 5992kb
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: 3ms
memory: 6312kb
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: 4ms
memory: 6308kb
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: 0ms
memory: 6308kb
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: 4ms
memory: 6304kb
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: 156ms
memory: 48156kb
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: 133ms
memory: 48200kb
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: 375ms
memory: 40636kb
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: 395ms
memory: 40628kb
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: 406ms
memory: 40632kb
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: 386ms
memory: 40612kb
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: 243ms
memory: 41684kb
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: 254ms
memory: 41648kb
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: 228ms
memory: 41864kb
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: 342ms
memory: 41256kb
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: 331ms
memory: 41260kb
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: 285ms
memory: 41268kb
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: 268ms
memory: 41332kb
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: 263ms
memory: 41396kb
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