codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```