1889.md (17769B)
1 Source: https://codeforces.com/blog/entry/121813 2 3 [1890A - Краска Дореми №3](/contest/1890/problem/A "Codeforces Round 906 (Div. 2)") 4 5 idea: [Cocoly1990](/profile/Cocoly1990 "Гроссмейстер Cocoly1990") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 By [Cocoly1990](/profile/Cocoly1990 "Гроссмейстер Cocoly1990") 14 15 ``` 16 // Time complexity O(nlogn) because of map 17 #include <bits/stdc++.h> 18 19 const int MX = 100 + 5; 20 21 int main() { 22 int t; 23 std::cin >> t; 24 while (t--) { 25 int n; 26 std::cin >> n; 27 std::map<int ,int> occ; 28 for (int i = 1; i <= n; ++i) { 29 int x; 30 std::cin >> x; 31 occ[x]++; 32 } 33 if (occ.size() >= 3) puts("No"); 34 else { 35 if (std::abs(occ.begin()->second - occ.rbegin()->second) <= 1) { 36 puts("Yes"); 37 } else { 38 puts("No"); 39 } 40 } 41 } 42 return 0; 43 } 44 ``` 45 46 [1890B - Циншань любит строки](/contest/1890/problem/B "Codeforces Round 906 (Div. 2)") 47 48 idea: [Imakf](/profile/Imakf "Гроссмейстер Imakf") 49 50 **Solution** 51 52 Tutorial is loading... 53 54 **Code** 55 56 By [Imakf](/profile/Imakf "Гроссмейстер Imakf") 57 58 ``` 59 #include <bits/stdc++.h> 60 61 bool ok(std::string s) { 62 for (size_t i = 1; i < s.length(); ++i) 63 if (s[i] == s[i - 1]) 64 return false; 65 return true; 66 } 67 68 void solve() { 69 std::string s, t; 70 int l1, l2; 71 std::cin >> l1 >> l2; 72 std::cin >> s >> t; 73 if (ok(s)) { 74 std::cout << "Yes" << std::endl; 75 return; 76 } 77 78 if (!ok(t) || *t.begin() != *t.rbegin()) { 79 std::cout << "No" << std::endl; 80 return; 81 } 82 83 int zz = 0, oo = 0; 84 for (size_t i = 1; i < s.length(); ++i) { 85 if (s[i] == s[i - 1]) { 86 if (s[i] == '0') zz = true; 87 if (s[i] == '1') oo = true; 88 } 89 } 90 91 if (zz && t[0] == '0') { 92 std::cout << "No" << std::endl; 93 return; 94 } 95 if (oo && t[0] == '1') { 96 std::cout << "No" << std::endl; 97 return; 98 } 99 100 std::cout << "Yes" << std::endl; 101 return; 102 } 103 104 int main() { 105 int t; 106 std::cin >> t; 107 while (t--) solve(); 108 return 0; 109 } 110 ``` 111 112 [1889A - Циншань любит строки 2](/contest/1889/problem/A "Codeforces Round 906 (Div. 1)") 113 114 idea: [Imakf](/profile/Imakf "Гроссмейстер Imakf") 115 116 **Solution** 117 118 Tutorial is loading... 119 120 **Code** 121 122 By [Imakf](/profile/Imakf "Гроссмейстер Imakf") 123 124 ``` 125 #include <bits/stdc++.h> 126 127 bool ok(std::string s) { 128 for (size_t i = 1; i < s.length(); ++i) 129 if (s[i] == s[i - 1]) 130 return false; 131 return true; 132 } 133 134 std::string s; 135 void solve() { 136 int n; std::cin >> n; 137 std::cin >> s; 138 int cnt0 = 0, cnt1 = 0; 139 for (int i = 0; i < s.length(); ++i) { 140 cnt0 += s[i] == '0'; 141 cnt1 += s[i] == '1'; 142 } 143 if (cnt0 != cnt1) { 144 std::cout << -1 << std::endl; 145 return; 146 } 147 std::vector<int> z; 148 std::deque<char> q; 149 for (int i = 0; i < s.length(); ++i) 150 q.push_back(s[i]); 151 152 int d = 0; 153 while (!q.empty()) { 154 if (q.front() == q.back()) { 155 if (q.front() == '0') { 156 q.push_back('0'); 157 q.push_back('1'); 158 z.push_back(n - d); 159 } else { 160 q.push_front('1'); 161 q.push_front('0'); 162 z.push_back(0 + d); 163 } 164 n += 2; 165 } 166 while (!q.empty() && q.front() != q.back()) { 167 q.pop_back(); 168 q.pop_front(); 169 ++d; 170 } 171 } 172 173 std::cout << z.size() << std::endl; 174 for (int i = 0; i < z.size(); ++i) { 175 std::cout << z[i]; 176 if (i + 1 == z.size()) std::cout << std::endl; 177 else std::cout << " "; 178 } 179 } 180 181 int main() { 182 int t; 183 std::cin >> t; 184 while (t--) solve(); 185 return 0; 186 } 187 ``` 188 189 [1889B - План подключения от Дореми](/contest/1889/problem/B "Codeforces Round 906 (Div. 1)") 190 191 idea: [Cocoly1990](/profile/Cocoly1990 "Гроссмейстер Cocoly1990") 192 193 **Solution** 194 195 Tutorial is loading... 196 197 **Code** 198 199 By [Cocoly1990](/profile/Cocoly1990 "Гроссмейстер Cocoly1990") 200 201 ``` 202 #include<bits/stdc++.h> 203 using i64 = long long; 204 using namespace std; 205 const int N = 5e5 + 7; 206 int T, n, C, p[N]; i64 a[N]; 207 void solve () { 208 cin >> n >> C; 209 for (int i = 1; i <= n; i ++) cin >> a[i]; 210 iota (p + 1, p + n + 1, 1); 211 sort (p + 1, p + n + 1, [&] (const int &u, const int &v) { 212 return 1ll * u * C - a[u] < 1ll * v * C - a[v]; 213 }); 214 i64 now = a[1]; 215 for (int i = 1, u; i <= n; i ++) { 216 u = p[i]; 217 if (u == 1) continue; 218 if (1ll * u * C > now + a[u]) return cout << "No\n", void (); 219 now += a[u]; 220 } 221 return cout << "Yes\n", void (); 222 } 223 int main () { 224 ios :: sync_with_stdio (false); cin.tie (0); cout.tie (0); 225 cin >> T; while (T --) solve (); 226 } 227 ``` 228 229 [1889C2 - План осушения от Дореми (сложная версия)](/contest/1889/problem/C2 "Codeforces Round 906 (Div. 1)") 230 231 idea: [waaitg](/profile/waaitg "Международный гроссмейстер waaitg"), [Imakf](/profile/Imakf "Гроссмейстер Imakf") 232 233 **Easy Solution** 234 235 Tutorial is loading... 236 237 **Hard Solution** 238 239 Tutorial is loading... 240 241 **Code** 242 243 By [Imakf](/profile/Imakf "Гроссмейстер Imakf") 244 245 ``` 246 #include <bits/stdc++.h> 247 248 #define debug(...) fprintf(stderr, __VA_ARGS__) 249 #define LL long long 250 251 const int MX = 2e5 + 23; 252 const int INF = 1e9; 253 254 void chkmax(int &x, int y) { 255 x = std::max(x, y); 256 } 257 258 struct Interval { 259 int l, r; 260 } I[MX]; 261 262 bool cmp(int x, int y) { 263 return I[x].l > I[y].l; 264 } 265 266 std::vector<int> add[MX], del[MX]; 267 int n, m, k, ban[MX]; 268 269 int st[21][MX][18], lg[MX]; 270 271 int query(int d, int l, int r) { 272 int len = lg[r - l + 1]; 273 return std::max(st[d][l][len], st[d][r - (1 << len) + 1][len]); 274 } 275 276 void change(int d, int p, int val) { 277 chkmax(st[d][p][0], val); 278 for (int i = 1; p - (1 << i) + 1 >= 0; ++i) { 279 st[d][p - (1 << i) + 1][i] = std::max( 280 st[d][p - (1 << i) + 1][i - 1], 281 st[d][p - (1 << (i - 1)) + 1][i - 1]); 282 } 283 } 284 285 void init() { 286 lg[0] = -1; 287 for (int i = 1; i <= n + 1; ++i) 288 lg[i] = lg[i - 1] + ((i & -i) == i); 289 for (int i = 1; i <= m; ++i) ban[i] = false; 290 for (int i = 1; i <= n + 1; ++i) { 291 add[i].clear(); 292 del[i].clear(); 293 } 294 for (int i = 0; i <= k; ++i) 295 for (int j = 0; j <= n; ++j) 296 for (int _k = 0; _k < 18; ++_k) 297 st[i][j][_k] = -INF; 298 } 299 300 void solve() { 301 scanf("%d%d%d", &n, &m, &k); 302 init(); 303 for (int i = 1; i <= m; ++i) { 304 int l, r; 305 scanf("%d%d", &l, &r); 306 I[i] = (Interval){l, r}; 307 add[l].push_back(i); 308 del[r + 1].push_back(i); 309 } 310 311 std::vector<int> cur, tmp; 312 313 change(0, 0, 0); 314 315 int uncover = 0, ans = 0; 316 int cnti = 0; 317 for (int i = 1; i <= n; ++i) { 318 for (auto j : add[i]) { 319 cur.push_back(j); 320 ++cnti; 321 } 322 323 for (auto j : del[i]) { 324 ban[j] = true; 325 --cnti; 326 } 327 328 if (cnti > k) { 329 for (int j = 0; j <= k; ++j) 330 change(j, i, -INF); 331 continue; 332 } 333 334 tmp.clear(); 335 for (auto j : cur) { 336 if (!ban[j]) { 337 tmp.push_back(j); 338 } 339 } 340 cur = tmp; 341 std::sort(cur.begin(), cur.end(), cmp); 342 343 if (cur.empty()) { 344 for (int j = 0; j <= k; ++j) 345 change(j, i, -INF); 346 ++uncover; 347 continue; 348 } 349 350 if (I[cur[0]].l <= i - 1) 351 for (int g = 0; g <= k; ++g) { 352 int z = query(g, I[cur[0]].l, i - 1); 353 chkmax(ans, z + 1); 354 change(g, i, z + 1); 355 } 356 else { 357 for (int g = 0; g <= k; ++g) { 358 change(g, i, -INF); 359 } 360 } 361 int cp = I[cur[0]].l - 1; 362 363 364 for (int j = 0; j < cur.size(); ++j) { 365 if (j + 1 != cur.size() && I[cur[j]].l == I[cur[j + 1]].l) 366 continue; 367 int np = (j + 1 == cur.size() ? 0 : I[cur[j + 1]].l); 368 for (int g = j + 1; g <= k; ++g) { 369 int z = query(g - (j + 1), np, cp); 370 chkmax(ans, z + 1); 371 change(g, i, z + 1); 372 // change(root[g], i, z + 1); 373 } 374 cp = np - 1; 375 } 376 } 377 printf("%d\n", ans + uncover); 378 } 379 380 int main() { 381 int t; scanf("%d", &t); 382 383 while (t--) solve(); 384 return 0; 385 } 386 ``` 387 388 [1889D - Игра со стеками](/contest/1889/problem/D "Codeforces Round 906 (Div. 1)") 389 390 idea: [waaitg](/profile/waaitg "Международный гроссмейстер waaitg") 391 392 **Solution** 393 394 Tutorial is loading... 395 396 **Code** 397 398 By [waaitg](/profile/waaitg "Международный гроссмейстер waaitg") 399 400 ``` 401 #include<stack> 402 #include<cstdio> 403 #include<cstring> 404 #include<iostream> 405 #include<algorithm> 406 using namespace std; 407 const int maxn=100005; 408 stack<int>s[maxn]; 409 int re[maxn],st[maxn],vis[maxn],tp; 410 int dfs(int u){ 411 if(re[u]) 412 return re[u]; 413 if(s[u].empty()) 414 return u; 415 if(vis[u]){ 416 st[tp+1]=0; 417 while(st[tp+1]!=u){ 418 s[st[tp]].pop(); 419 vis[st[tp]]=0; 420 --tp; 421 } 422 return dfs(u); 423 } 424 st[vis[u]=++tp]=u; 425 return dfs(s[u].top()); 426 } 427 int main(){ 428 int n;scanf("%d",&n); 429 for(int i=1;i<=n;++i){ 430 int k;scanf("%d",&k); 431 while(k--){ 432 int c;scanf("%d",&c); 433 s[i].push(c); 434 } 435 } 436 for(int i=1;i<=n;++i){ 437 tp=0;int ok=dfs(i); 438 for(int j=1;j<=tp;++j) 439 re[st[j]]=ok; 440 printf("%d%c",ok," \n"[i==n]); 441 } 442 return 0; 443 } 444 ``` 445 446 [1889E - Обменные деревья Дореми](/contest/1889/problem/E "Codeforces Round 906 (Div. 1)") 447 448 idea: [waaitg](/profile/waaitg "Международный гроссмейстер waaitg") 449 450 **Solution** 451 452 Tutorial is loading... 453 454 **Code** 455 456 By [waaitg](/profile/waaitg "Международный гроссмейстер waaitg") 457 458 ``` 459 #include<vector> 460 #include<cstdio> 461 #include<cstring> 462 #include<iostream> 463 #include<algorithm> 464 using namespace std; 465 const int maxn=100005; 466 struct Edge{ 467 int v,nt; 468 Edge(int v=0,int nt=0): 469 v(v),nt(nt){} 470 }eG[maxn*160]; 471 int hdG[maxn*40],numG; 472 void qwqG(int u,int v){ 473 eG[++numG]=Edge(v,hdG[u]);hdG[u]=numG; 474 } 475 int tot; 476 struct AnTree{ 477 struct Edge{ 478 int v,nt; 479 Edge(int v=0,int nt=0): 480 v(v),nt(nt){} 481 }e[maxn*2]; 482 int hd[maxn],num; 483 void qwq(int u,int v){ 484 e[++num]=Edge(v,hd[u]),hd[u]=num; 485 } 486 int n; 487 void init(int n){ 488 this->n=n; 489 for(int i=1;i<n;++i){ 490 int u,v; 491 scanf("%d%d",&u,&v); 492 qwq(u,v);qwq(v,u); 493 } 494 } 495 int pa[maxn][20],id[maxn][20],dp[maxn]; 496 void dfs(int u,int p){ 497 if(p==0)dp[u]=0; 498 for(int i=1;(1<<i)<=dp[u];++i) 499 pa[u][i]=pa[pa[u][i-1]][i-1]; 500 for(int i=hd[u];i;i=e[i].nt){ 501 int v=e[i].v; 502 if(v==p)continue; 503 dp[v]=dp[u]+1; 504 pa[v][0]=u; 505 id[v][0]=++tot; 506 dfs(v,u); 507 } 508 } 509 int getid(int u,int d){ 510 int&re=id[u][d]; 511 if(re)return re; 512 re=++tot; 513 qwqG(re,getid(u,d-1)); 514 qwqG(re,getid(pa[u][d-1],d-1)); 515 return re; 516 } 517 void link(int x,int u,int v){ 518 if(dp[u]<dp[v])swap(u,v); 519 for(int t=dp[u]-dp[v],cn=0;t;t>>=1,++cn) 520 if(t&1)qwqG(x,getid(u,cn)),u=pa[u][cn]; 521 if(u==v)return; 522 int t=0;while(dp[u]>>t)++t; 523 while(t--){ 524 if(pa[u][t]!=pa[v][t]){ 525 qwqG(x,getid(u,t)); 526 qwqG(x,getid(v,t)); 527 u=pa[u][t];v=pa[v][t]; 528 } 529 } 530 qwqG(x,getid(u,0)); 531 qwqG(x,getid(v,0)); 532 } 533 void erase(void){ 534 for(int i=1;i<=n;++i){ 535 hd[i]=0,dp[i]=0;int j=0; 536 while(pa[i][j])pa[i][j++]=0; 537 j=0;while(id[i][j])id[i][j++]=0; 538 } 539 num=0; 540 } 541 int parent(int u){ 542 return pa[u][0]; 543 } 544 int identity(int u){ 545 return id[u][0]; 546 } 547 }T1,T2; 548 int dfn[maxn*40],low[maxn*40],cnt; 549 int st[maxn*40],tp,in[maxn*40]; 550 int scc[maxn*40],scn; 551 int vis[maxn*40]; 552 void tarjan(int u){ 553 dfn[u]=low[u]=++cnt; 554 in[st[++tp]=u]=true; 555 for(int i=hdG[u];i;i=eG[i].nt){ 556 int v=eG[i].v; 557 if(!dfn[v]){ 558 tarjan(v); 559 low[u]=min(low[u],low[v]); 560 } 561 else if(in[v]) 562 low[u]=min(low[u],dfn[v]); 563 } 564 if(dfn[u]==low[u]){ 565 ++scn; 566 st[tp+1]=0; 567 while(st[tp+1]!=u){ 568 in[st[tp]]=false; 569 scc[st[tp]]=scn; 570 --tp; 571 } 572 } 573 } 574 const int mod=1e9+7; 575 int power(int a,int x){ 576 int re=1; 577 while(x){ 578 if(x&1)re=1ll*re*a%mod; 579 a=1ll*a*a%mod,x>>=1; 580 } 581 return re; 582 } 583 void solve(void){ 584 int n;scanf("%d",&n); 585 T1.init(n);T2.init(n); 586 T1.dfs(1,0);T2.dfs(1,0); 587 int rec=tot; 588 for(int i=2;i<=n;++i){ 589 T2.link(T1.identity(i),i,T1.parent(i)); 590 T1.link(T2.identity(i),i,T2.parent(i)); 591 } 592 for(int i=1;i<=tot;++i) 593 if(!dfn[i])tarjan(i); 594 for(int i=1;i<=rec;++i) 595 ++vis[scc[i]]; 596 int ANS=0; 597 for(int i=1;i<=scn;++i){ 598 if(vis[i])++ANS; 599 vis[i]=0; 600 } 601 for(int u=1;u<=rec;++u){ 602 if(eG[hdG[u]].nt==0){ 603 int v=eG[hdG[u]].v; 604 if(u<v&&eG[hdG[v]].nt==0){ 605 if(eG[hdG[v]].v==u){ 606 --ANS; 607 } 608 } 609 } 610 } 611 ANS=power(2,ANS); 612 printf("%d\n",ANS); 613 for(int i=1;i<=tot;++i){ 614 hdG[i]=0; 615 dfn[i]=low[i]=scc[i]=0; 616 } 617 tot=cnt=scn=numG=0; 618 T1.erase();T2.erase(); 619 } 620 int main(){ 621 // freopen("test","r",stdin); 622 // freopen("out","w",stdout); 623 int T;scanf("%d",&T); 624 while(T--)solve(); 625 return 0; 626 } 627 ``` 628 629 [1889F - Усреднённое дерево Дореми](/contest/1889/problem/F "Codeforces Round 906 (Div. 1)") 630 631 idea: [waaitg](/profile/waaitg "Международный гроссмейстер waaitg"), [Imakf](/profile/Imakf "Гроссмейстер Imakf") 632 633 **Solution** 634 635 Tutorial is loading... 636 637 **Code** 638 639 By [waaitg](/profile/waaitg "Международный гроссмейстер waaitg") 640 641 ``` 642 #include<cstdio> 643 #include<cstring> 644 #include<iostream> 645 #include<algorithm> 646 #define ch() getchar() 647 #define pc(x) putchar(x) 648 using namespace std; 649 template<typename T>void read(T&x){ 650 static char c;static int f; 651 for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f; 652 for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f; 653 } 654 template<typename T>void write(T x){ 655 static char q[64];int cnt=0; 656 if(x==0)return pc('0'),void(); 657 if(x<0)pc('-'),x=-x; 658 while(x)q[cnt++]=x%10+'0',x/=10; 659 while(cnt--)pc(q[cnt]); 660 } 661 long long gcd(long long a,long long b){ 662 if(b==0)return a; 663 return gcd(b,a%b); 664 } 665 struct Frac{ 666 long long a; 667 int b;// a/b 668 Frac(long long a=0,int b=1): 669 a(a),b(b){} 670 bool operator < (const Frac o)const{ 671 return a*o.b<o.a*b; 672 } 673 bool operator > (const Frac o)const{ 674 return a*o.b>o.a*b; 675 } 676 bool operator == (const Frac o)const{ 677 return a*o.b==o.a*b; 678 } 679 void output(){ 680 printf("%lld/%d",a,b); 681 } 682 }; 683 const int inf=0x3f3f3f3f; 684 struct Val{ 685 int p1,p2;Frac v1,v2; 686 Val(int p1=inf,int p2=inf,Frac v1=Frac(),Frac v2=Frac()): 687 p1(p1),p2(p2),v1(v1),v2(v2){} 688 void output(void){ 689 printf("%d : ",p1);v1.output();puts(""); 690 printf("%d : ",p2);v2.output();puts("\n"); 691 } 692 }; 693 Val Comb(Val A,Val B){ 694 if(A.p1>B.p1)swap(A,B); 695 if(B.v1==A.v1) 696 return Val(A.p1,A.p2<B.p2?A.p2:B.p2,A.v1,A.p2<B.p2?A.v2:B.v2); 697 return Val(A.p1,A.p2<B.p1?A.p2:B.p1,A.v1,A.p2<B.p1?A.v2:B.v1); 698 } 699 const int maxn=10005,maxk=505; 700 struct Edge{ 701 int v,nt; 702 Edge(int v=0,int nt=0): 703 v(v),nt(nt){} 704 }e[maxn*2]; 705 int hd[maxn],num; 706 void qwq(int u,int v){ 707 e[++num]=Edge(v,hd[u]),hd[u]=num; 708 } 709 long long sm[maxn];int sz[maxn]; 710 int dp[maxn][maxk],wp[maxn][maxk],k,n; 711 Val va[maxn][maxk]; 712 void Merge(int x,int l,int r,int L,int R){ 713 wp[x][0]=0; 714 va[x][0]=Comb(va[l][0],va[r][0]); 715 L=min(L,k);R=min(R,k); 716 int up=min(L+R,k); 717 for(int i=1;i<=up;++i){ 718 int t=wp[x][i]=min(L,i),cl=inf,cr=inf; 719 while(t>0&&i-t<R){ 720 cl=min(cl,dp[l][t]);--t; 721 cr=min(cr,dp[r][i-t]); 722 if(cr<cl)wp[x][i]=t,cl=cr=inf; 723 } 724 t=wp[x][i-1];cl=cr=inf; 725 if(wp[x][i-1]<wp[x][i]){ 726 while(t<wp[x][i])cl=min(cl,dp[l][++t]); 727 dp[x][i]=cl; 728 } 729 else{ 730 while(i-t-1<i-wp[x][i])cr=min(cr,dp[r][i-(t--)]); 731 dp[x][i]=cr; 732 } 733 va[x][i]=Comb(va[l][wp[x][i]],va[r][i-wp[x][i]]); 734 } 735 } 736 int MN[maxn],rsz[maxn]; 737 long long val[maxn]; 738 void dfs(int u,int p){ 739 int l=0,fa=0;sm[u]=val[u]; 740 sz[u]=0;rsz[u]=1;MN[u]=0; 741 for(int i=hd[u];i;i=e[i].nt){ 742 int v=e[i].v; 743 if(v==p){fa=i;continue;}dfs(v,u); 744 Merge(i,i^1,l,sz[v],sz[u]); 745 sm[u]+=sm[v],sz[u]+=sz[v]; 746 rsz[u]+=rsz[v]; 747 l=i; 748 } 749 if(sz[u]==0){ 750 ++sz[u];MN[u]=1; 751 va[fa][0]=va[fa][1]=Val(u,inf,val[u]); 752 dp[fa][1]=inf; 753 } 754 else{ 755 int up=min(sz[u],k); 756 for(int i=0;i<=up;++i) 757 va[fa][i]=Comb(va[l][i],Val(u,inf,val[u])),dp[fa][i]=dp[l][i]; 758 Frac tmp(sm[u],rsz[u]); 759 for(int i=1;i<=up;++i) 760 if(va[fa][i].v1>tmp||(va[fa][i].v1==tmp&&va[fa][i].v2>tmp)) 761 va[fa][i]=Val(va[fa][i].p1,inf,tmp),MN[u]=i; 762 if(MN[u]){ 763 if(va[fa][0].v1==va[fa][1].v1) 764 dp[fa][1]=va[fa][0].p2; 765 else 766 dp[fa][1]=va[fa][0].p1; 767 for(int i=2;i<=MN[u];++i) 768 dp[fa][i]=inf; 769 if(MN[u]<up){ 770 if(va[fa][MN[u]].v1==va[fa][MN[u]+1].v1) 771 dp[fa][MN[u]+1]=va[fa][MN[u]+1].p2; 772 else 773 dp[fa][MN[u]+1]=va[fa][MN[u]+1].p1; 774 } 775 } 776 }/* 777 int up=min(sz[u],k); 778 printf("%d MN:%d\n",u,MN[u]); 779 for(int i=1;i<=up;++i) 780 printf("dp %d = %d\n",i,dp[fa][i]);*/ 781 } 782 int st[maxn],ts; 783 int que[maxn],cnt; 784 void solve(int u,int p,int sk){ 785 if(sk==0)return;sk=min(sk,sz[u]); 786 if(sk<=MN[u])return st[++ts]=u,void(); 787 int tnc=cnt; 788 for(int i=hd[u];i;i=e[i].nt){ 789 int v=e[i].v; 790 if(v==p)continue; 791 que[cnt++]=i; 792 } 793 for(int j=cnt-1;j>=tnc;--j){ 794 int i=que[j]; 795 solve(e[i].v,u,wp[i][sk]); 796 sk-=wp[i][sk]; 797 } 798 } 799 void imple(void){ 800 int r; 801 read(n),read(r),read(k); 802 for(int i=1;i<=n;++i) 803 read(val[i]); 804 qwq(r,0); 805 for(int i=1;i<n;++i){ 806 int u,v;read(u),read(v); 807 qwq(u,v);qwq(v,u); 808 } 809 dfs(r,0); 810 solve(r,0,k); 811 printf("%d\n",ts); 812 for(int i=1;i<=ts;++i) 813 printf("%d%c",st[i]," \n"[i==ts]); 814 for(int i=0;i<=n;++i)hd[i]=0; 815 num=cnt=ts=0; 816 } 817 int main(){ 818 // freopen("test","r",stdin); 819 int T;read(T); 820 while(T--)imple(); 821 return 0; 822 } 823 ```