codeforces-scrape

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

1010.md (22549B)


      1 Source: https://codeforces.com/blog/entry/60851
      2 
      3 [1011A - Stages](/contest/1011/problem/A "Codeforces Round 499 (Div. 2)")
      4 
      5 Author: Mike Mirzayanov ([MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")).
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main()
     19 {
     20     int n,k;
     21     cin>>n>>k;
     22     string s;
     23     cin>>s;
     24     sort(s.begin(),s.end());
     25     char last='a'-2;
     26     int ans=0;
     27     int len=0;
     28     for(int i=0;i<n;i++)
     29         if(s[i]>=last+2)
     30         {
     31             last=s[i];
     32             ans+=s[i]-'a'+1;
     33             len++;
     34             if(len>=k)
     35                 cout<<ans,exit(0);
     36         }
     37     cout<<-1;
     38 }
     39 ```
     40 
     41 [1011B - Planning The Expedition](/contest/1011/problem/B "Codeforces Round 499 (Div. 2)")
     42 
     43 Author: Mike Mirzayanov ([MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")).
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53 
     54 using namespace std;
     55 
     56 const int N = 100;
     57 
     58 int main() {
     59     int n, m;
     60     cin >> n >> m;
     61     vector<int> c(N + 1);
     62     for (int i = 0; i < m; i++) {
     63         int a;
     64         cin >> a;
     65         c[a]++;
     66     }
     67     for (int d = N; d >= 1; d--) {
     68         vector<int> cc(c);
     69         int k = 0;
     70         for (int i = 1; i <= N; i++)
     71             while (cc[i] >= d) {
     72                 k++;
     73                 cc[i] -= d;
     74             }
     75         if (k >= n) {
     76             cout << d << endl;
     77             return 0;
     78         }
     79     }
     80     cout << 0 << endl;
     81 }
     82 ```
     83 
     84 [1011C - Fly](/contest/1011/problem/C "Codeforces Round 499 (Div. 2)") / [1010A - Fly](/contest/1010/problem/A "Codeforces Round 499 (Div. 1)")
     85 
     86 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")).
     87 
     88 **Tutorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Solution**
     93 
     94 ```
     95 #include<bits/stdc++.h>
     96 
     97 using namespace std;
     98 
     99 int main()
    100 {
    101     int n,m;
    102     cin>>n>>m;
    103     int a[n];
    104     for(int i=0;i<n;i++)
    105     {
    106         cin>>a[i];
    107         if(a[i]<=1)
    108         {
    109             printf("-1\n");
    110             exit(0);
    111         }
    112     }
    113     int b[n];
    114     for(int i=0;i<n;i++)
    115     {
    116         cin>>b[i];
    117         if(b[i]<=1)
    118         {
    119             printf("-1\n");
    120             exit(0);
    121         }
    122     }
    123     double s=m;
    124     s+=s/(a[0]-1);
    125     for(int i=n-1;i>=1;i--)
    126     {
    127         s+=s/(b[i]-1);
    128         s+=s/(a[i]-1);
    129     }
    130     s+=s/(b[0]-1);
    131     printf("%.10lf\n",s-m);
    132 }
    133 ```
    134 
    135 [1011D - Rocket](/contest/1011/problem/D "Codeforces Round 499 (Div. 2)") / [1010B - Rocket](/contest/1010/problem/B "Codeforces Round 499 (Div. 1)")
    136 
    137 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")).
    138 
    139 **Tutorial**
    140 
    141 Tutorial is loading...
    142 
    143 **Solution**
    144 
    145 ```
    146 #include <bits/stdc++.h>
    147 
    148 using namespace std;
    149 
    150 int query(int y)
    151 {
    152     cout<<y<<"\n";
    153     fflush(stdout);
    154     int t;
    155     cin>>t;
    156     if(t==0||t==-2)
    157         exit(0);
    158     return t;
    159 }
    160 
    161 int main()
    162 {
    163     int m,n;
    164     cin>>m>>n;
    165     int p[n];
    166     for(int i=0;i<n;i++)
    167     {
    168         int t=query(1);
    169         p[i]=t==1;
    170     }
    171     int l=2,r=m;
    172     for(int q=0;;q++)
    173     {
    174         int y=(l+r)/2;
    175         int t=query(y);
    176         if(!p[q%n])
    177             t*=-1;
    178         if(t==1)
    179             l=y+1;
    180         else
    181             r=y-1;
    182     }
    183 }
    184 ```
    185 
    186 [1011E - Border](/contest/1011/problem/E "Codeforces Round 499 (Div. 2)") / [1010C - Border](/contest/1010/problem/C "Codeforces Round 499 (Div. 1)")
    187 
    188 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")).
    189 
    190 **Tutorial**
    191 
    192 Tutorial is loading...
    193 
    194 **Solution**
    195 
    196 ```
    197 #include<bits/stdc++.h>
    198 
    199 using namespace std;
    200 
    201 int gcd(int a,int b)
    202 {
    203     if(a<b)
    204         swap(a,b);
    205     return (b==0)?a:gcd(b,a%b);
    206 }
    207 
    208 int main()
    209 {
    210     int n,k;
    211     scanf("%d%d",&n,&k);
    212     int g=0;
    213     for(int i=0;i<n;i++)
    214     {
    215         int t;
    216         scanf("%d",&t);
    217         g=gcd(g,t);
    218     }
    219     set<int> ans;
    220     for(long long i=0,s=0;i<k;i++,s+=g)
    221         ans.insert(s%k);
    222     printf("%d\n",ans.size());
    223     for(set<int>::iterator i=ans.begin();i!=ans.end();i++)
    224         printf("%d ",*i);
    225 }
    226 ```
    227 
    228 [1011F - Mars rover](/contest/1011/problem/F "Codeforces Round 499 (Div. 2)") / [1010D - Mars rover](/contest/1010/problem/D "Codeforces Round 499 (Div. 1)")
    229 
    230 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")).
    231 
    232 **Tutorial**
    233 
    234 Tutorial is loading...
    235 
    236 **Solution**
    237 
    238 ```
    239 #pragma GCC optimize("O3")
    240 #include<bits/stdc++.h>
    241 
    242 using namespace std;
    243 
    244 struct vertex
    245 {
    246     char type;
    247     vector<int>in;
    248     bool val;
    249     bool change;
    250 };
    251 
    252 int n;
    253 vector<vertex> g;
    254 
    255 int dfs1(int v)
    256 {
    257     switch(g[v].type)
    258     {
    259     case 'A':
    260         g[v].val = dfs1(g[v].in[0]) & dfs1(g[v].in[1]);
    261         break;
    262     case 'O':
    263         g[v].val = dfs1(g[v].in[0]) | dfs1(g[v].in[1]);
    264         break;
    265     case 'X':
    266         g[v].val = dfs1(g[v].in[0]) ^ dfs1(g[v].in[1]);
    267         break;
    268     case 'N':
    269         g[v].val = ! dfs1(g[v].in[0]);
    270         break;
    271     }
    272     return g[v].val;
    273 }
    274 
    275 void dfs2(int v)
    276 {
    277     if(g[v].change==false)
    278         for(int i=0;i<g[v].in.size();i++)
    279             g[g[v].in[i]].change=false;
    280     else
    281         switch(g[v].type)
    282         {
    283         case 'A':
    284             if(g[v].val==(!g[g[v].in[0]].val&g[g[v].in[1]].val)) /// equal to if(g[g[v].in[1]].val==false)
    285                 g[g[v].in[0]].change=false;
    286             else
    287                 g[g[v].in[0]].change=true;
    288             if(g[v].val==(g[g[v].in[0]].val&!g[g[v].in[1]].val)) /// equal to if(g[g[v].in[0]].val==false)
    289                 g[g[v].in[1]].change=false;
    290             else
    291                 g[g[v].in[1]].change=true;
    292             break;
    293         case 'O':
    294             if(g[v].val==(!g[g[v].in[0]].val|g[g[v].in[1]].val)) /// equal to if(g[g[v].in[1]].val==true)
    295                 g[g[v].in[0]].change=false;
    296             else
    297                 g[g[v].in[0]].change=true;
    298             if(g[v].val==(g[g[v].in[0]].val|!g[g[v].in[1]].val)) /// equal to if(g[g[v].in[0]].val==true)
    299                 g[g[v].in[1]].change=false;
    300             else
    301                 g[g[v].in[1]].change=true;
    302             break;
    303         case 'X':
    304             if(g[v].val==(!g[g[v].in[0]].val^g[g[v].in[1]].val)) /// equal to if(false)
    305                 g[g[v].in[0]].change=false;
    306             else
    307                 g[g[v].in[0]].change=true;
    308             if(g[v].val==(g[g[v].in[0]].val^!g[g[v].in[1]].val)) /// equal to if(false)
    309                 g[g[v].in[1]].change=false;
    310             else
    311                 g[g[v].in[1]].change=true;
    312             break;
    313         case 'N':
    314             if(g[v].val==(!!g[g[v].in[0]].val)) /// equal to if(false)
    315                 g[g[v].in[0]].change=false;
    316             else
    317                 g[g[v].in[0]].change=true;
    318             break;
    319         }
    320     for(int i=0;i<g[v].in.size();i++)
    321         dfs2(g[v].in[i]);
    322 }
    323 
    324 int main()
    325 {
    326     scanf("%d",&n);
    327     g.resize(n);
    328     for(int i=0;i<n;i++)
    329     {
    330         char c[4];
    331         scanf("%s",c);
    332         g[i].type=c[0];
    333         int x;
    334         switch(g[i].type)
    335         {
    336         case 'I':
    337             scanf("%d",&x);
    338             g[i].val=x;
    339             break;
    340         case 'N':
    341             scanf("%d",&x);
    342             g[i].in.push_back(x-1);
    343             break;
    344         default:
    345             scanf("%d",&x);
    346             g[i].in.push_back(x-1);
    347             scanf("%d",&x);
    348             g[i].in.push_back(x-1);
    349             break;
    350         }
    351     }
    352     dfs1(0);
    353     g[0].change=true;
    354     dfs2(0);
    355     for(int i=0;i<n;i++)
    356         if(g[i].type=='I')
    357             printf("%d",g[0].val^g[i].change);
    358 }
    359 ```
    360 
    361 [1010E - Store](/contest/1010/problem/E "Codeforces Round 499 (Div. 1)")
    362 
    363 Author: Vladislav Zavodnik ([VladProg](/profile/VladProg "Master VladProg")).
    364 
    365 **Tutorial**
    366 
    367 Tutorial is loading...
    368 
    369 **Solution**
    370 
    371 ```
    372 #include<bits/stdc++.h>
    373 
    374 using namespace std;
    375 
    376 int xmax,ymax,zmax,n,m,k;
    377 
    378 map< int , map< int , pair< int ,int > > > pmap;
    379 vector< pair< int , map< int , pair< int ,int > > > > pvector;
    380 vector< pair< vector< pair< int , pair< int , int > > > , vector< pair< int , int > > > > tree;
    381 int oxl,oxr,oyl,oyr,ozl,ozr;
    382 
    383 pair<int,int> comb(pair<int,int> p1,pair<int,int> p2)
    384 {
    385     return make_pair(max(p1.first,p2.first),
    386                      min(p1.second,p2.second));
    387 }
    388 
    389 void build_y(int vx,int lxt, int rxt,int vy,int lyt, int ryt)
    390 {
    391     if(lyt==ryt)
    392     {
    393         if(lxt==rxt)
    394             tree[vx].second[vy]=tree[vx].first[lyt].second;
    395         else
    396         {
    397             int sl,sr;
    398             sl=0,sr=tree[vx*2+1].first.size()-1;
    399             while(sr>sl)
    400             {
    401                 int sm=(sl+sr)/2;
    402                 if(tree[vx*2+1].first[sm].first>=tree[vx].first[lyt].first)
    403                     sr=sm;
    404                 else
    405                     sl=sm+1;
    406             }
    407             pair<int,int> res1=(tree[vx*2+1].first[sl].first==tree[vx].first[lyt].first)?
    408                                (tree[vx*2+1].first[sl].second):
    409                                 make_pair(0,(int)zmax+1);
    410             sl=0,sr=tree[vx*2+2].first.size()-1;
    411             while(sr>sl)
    412             {
    413                 int sm=(sl+sr)/2;
    414                 if(tree[vx*2+2].first[sm].first>=tree[vx].first[lyt].first)
    415                     sr=sm;
    416                 else
    417                     sl=sm+1;
    418             }
    419             pair<int,int> res2=(tree[vx*2+2].first[sl].first==tree[vx].first[lyt].first)?
    420                                (tree[vx*2+2].first[sl].second):
    421                                 make_pair(0,(int)zmax+1);
    422             tree[vx].second[vy]=comb(res1,res2);
    423         }
    424     }
    425     else
    426     {
    427         int myt=(lyt+ryt)/2;
    428         build_y(vx,lxt,rxt,vy*2+1,lyt,myt);
    429         build_y(vx,lxt,rxt,vy*2+2,myt+1,ryt);
    430         tree[vx].second[vy]=comb(tree[vx].second[vy*2+1],tree[vx].second[vy*2+2]);
    431     }
    432 }
    433 
    434 void build_x(int vx,int lxt, int rxt)
    435 {
    436     if(lxt==rxt)
    437         tree[vx].first=vector< pair< int , pair< int , int > > >(pvector[lxt].second.begin(),pvector[lxt].second.end());
    438     else
    439     {
    440         int mxt=(lxt+rxt)/2;
    441         build_x(2*vx+1,lxt,mxt);
    442         build_x(2*vx+2,mxt+1,rxt);
    443         for(vector< pair< int , pair< int , int > > >::iterator i=tree[2*vx+1].first.begin(),j=tree[2*vx+2].first.begin();;)
    444         {
    445             if(i==tree[2*vx+1].first.end())
    446             {
    447                 for(;j!=tree[2*vx+2].first.end();j++)
    448                     tree[vx].first.push_back(*j);
    449                 break;
    450             }
    451             if(j==tree[2*vx+2].first.end())
    452             {
    453                 for(;i!=tree[2*vx+1].first.end();i++)
    454                     tree[vx].first.push_back(*i);
    455                 break;
    456             }
    457             if(i->first<j->first)
    458             {
    459                 tree[vx].first.push_back(*i);
    460                 i++;
    461             }
    462             else if(j->first<i->first)
    463             {
    464                 tree[vx].first.push_back(*j);
    465                 j++;
    466             }
    467             else
    468             {
    469                 tree[vx].first.push_back(make_pair(i->first,comb(i->second,j->second)));
    470                 i++;
    471                 j++;
    472             }
    473         }
    474     }
    475     tree[vx].second.resize(tree[vx].first.size()*4);
    476     build_y(vx,lxt,rxt,0,0,tree[vx].first.size()-1);
    477 }
    478 
    479 pair<int,int> get_y(int vx, int vy, int lyt, int ryt, int lyc, int ryc)
    480 {
    481     if(lyc>ryc)
    482         return make_pair(0,zmax+1);
    483     if(lyc==lyt&&ryt==ryc)
    484         return tree[vx].second[vy];
    485     int myt=(lyt+ryt)/2;
    486     return comb(get_y(vx,vy*2+1,lyt,myt,lyc,min(ryc,myt)),
    487                 get_y(vx,vy*2+2,myt+1,ryt,max(lyc,myt+1),ryc));
    488 }
    489 
    490 pair<int,int> get_x(int vx, int lxt, int rxt, int lxc, int rxc, int ly, int ry)
    491 {
    492     if(lxc>rxc)
    493         return make_pair(0,zmax+1);
    494     if(lxc==lxt&&rxt==rxc)
    495     {
    496         int sl,sr;
    497         sl=0,sr=tree[vx].first.size()-1;
    498         while(sr>sl)
    499         {
    500             int sm=(sl+sr)/2;
    501             if(tree[vx].first[sm].first>=ly)
    502                 sr=sm;
    503             else
    504                 sl=sm+1;
    505         }
    506         int lyc=sl;
    507         sl=0,sr=tree[vx].first.size()-1;
    508         while(sr>sl)
    509         {
    510             int sm=(sl+sr+1)/2;
    511             if(tree[vx].first[sm].first<=ry)
    512                 sl=sm;
    513             else
    514                 sr=sm-1;
    515         }
    516         int ryc=sr;
    517         return (tree[vx].first[lyc].first>=ly&&tree[vx].first[ryc].first<=ry)?
    518                get_y(vx,0,0,tree[vx].first.size()-1,lyc,ryc):
    519                make_pair(0,(int)zmax+1);
    520     }
    521     int mxt=(lxt+rxt)/2;
    522     return comb(get_x(vx*2+1,lxt,mxt,lxc,min(rxc,mxt),ly,ry),
    523                 get_x(vx*2+2,mxt+1,rxt,max(lxc,mxt+1),rxc,ly,ry));
    524 }
    525 
    526 int main()
    527 {
    528     scanf("%d%d%d%d%d%d",&xmax,&ymax,&zmax,&n,&m,&k);
    529     oxl=xmax;
    530     oxr=1;
    531     oyl=ymax;
    532     oyr=1;
    533     ozl=zmax;
    534     ozr=1;
    535     for(int i=0;i<n;i++)
    536     {
    537         int x,y,z;
    538         scanf("%d%d%d",&x,&y,&z);
    539         oxl=min(oxl,x);
    540         oxr=max(oxr,x);
    541         oyl=min(oyl,y);
    542         oyr=max(oyr,y);
    543         ozl=min(ozl,z);
    544         ozr=max(ozr,z);
    545     }
    546     for(int i=0;i<m;i++)
    547     {
    548         int x,y,z;
    549         scanf("%d%d%d",&x,&y,&z);
    550         if(oxl<=x&&x<=oxr&&oyl<=y&&y<=oyr&&ozl<=z&&z<=ozr)
    551         {
    552             printf("INCORRECT\n");
    553             exit(0);
    554         }
    555         map< int , pair< int ,int > >::iterator it=pmap[x].insert(make_pair(y,make_pair(0,zmax+1))).first;
    556         if(z<=ozr)
    557             it->second.first=max(it->second.first,z);
    558         if(z>=ozl)
    559             it->second.second=min(it->second.second,z);
    560     }
    561     printf("CORRECT\n");
    562     if(m>0)
    563     {
    564         pvector=vector< pair< int , map< int , pair< int ,int > > > >(pmap.begin(),pmap.end());
    565         tree.resize(pvector.size()*4);
    566         build_x(0,0,pvector.size()-1);
    567     }
    568     for(int i=0;i<k;i++)
    569     {
    570         int x,y,z;
    571         scanf("%d%d%d",&x,&y,&z);
    572         if(oxl<=x&&x<=oxr&&oyl<=y&&y<=oyr&&ozl<=z&&z<=ozr)
    573         {
    574             printf("OPEN\n");
    575             continue;
    576         }
    577         if(m==0)
    578         {
    579             printf("UNKNOWN\n");
    580             continue;
    581         }
    582         bool closed=false;
    583         for(int ii=0;ii<=1;ii++)
    584             for(int jj=0;jj<=1;jj++)
    585             {
    586                 if(closed)
    587                     break;
    588                 int i=oxl+ii*(oxr-oxl);
    589                 int j=oyl+jj*(oyr-oyl);
    590                 int lx=min(x,i),rx=max(x,i);
    591                 int sl,sr;
    592                 sl=0,sr=pvector.size()-1;
    593                 while(sr>sl)
    594                 {
    595                     int sm=(sl+sr)/2;
    596                     if(pvector[sm].first>=lx)
    597                         sr=sm;
    598                     else
    599                         sl=sm+1;
    600                 }
    601                 int lxc=sl;
    602                 sl=0,sr=pvector.size()-1;
    603                 while(sr>sl)
    604                 {
    605                     int sm=(sl+sr+1)/2;
    606                     if(pvector[sm].first<=rx)
    607                         sl=sm;
    608                     else
    609                         sr=sm-1;
    610                 }
    611                 int rxc=sr;
    612                 if(pvector[lxc].first>=lx&&pvector[rxc].first<=rx)
    613                 {
    614                     pair<int,int> p=get_x(0,0,pvector.size()-1,lxc,rxc,min(y,j),max(y,j));
    615                     if(min({z,ozl,ozr})<=p.first||max({z,ozl,ozr})>=p.second)
    616                         closed=true;
    617                 }
    618             }
    619         if(closed)
    620             printf("CLOSED\n");
    621         else
    622             printf("UNKNOWN\n");
    623     }
    624 }
    625 ```
    626 
    627 [1010F - Tree](/contest/1010/problem/F "Codeforces Round 499 (Div. 1)")
    628 
    629 Authors: Ildar Gainullin ([300iq](/profile/300iq "Grandmaster 300iq")) and Dmitry Sayutin ([cdkrot](/profile/cdkrot "International Master cdkrot")).
    630 
    631 **Tutorial**
    632 
    633 Tutorial is loading...
    634 
    635 **Solution**
    636 
    637 ```
    638 #include <cmath>
    639 #include <iostream>
    640 #include <vector>
    641 #include <algorithm>
    642 #include <string>
    643 #include <set>
    644 #include <map>
    645 #include <list>
    646 #include <time.h>
    647 #include <math.h>
    648 #include <random>
    649 #include <deque>
    650 #include <queue>
    651 #include <cassert>
    652 #include <unordered_map>
    653 #include <unordered_set>
    654 #include <iomanip>
    655 #include <bitset>
    656 #include <sstream>
    657 
    658 using namespace std;
    659 
    660 typedef long long ll;
    661 
    662 mt19937 rnd(228);
    663 
    664 const int md = 998244353;
    665 
    666 inline void add(int &a, int b) {
    667   a += b;
    668   if (a >= md) a -= md;
    669 }
    670 
    671 inline void sub(int &a, int b) {
    672   a -= b;
    673   if (a < 0) a += md;
    674 }
    675 
    676 inline int mul(int a, int b) {
    677 #if !defined(_WIN32) || defined(_WIN64)
    678   return (int) ((long long) a * b % md);
    679 #endif
    680   unsigned long long x = (long long) a * b;
    681   unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    682   asm(
    683     "divl %4; \n\t"
    684     : "=a" (d), "=d" (m)
    685     : "d" (xh), "a" (xl), "r" (md)
    686   );
    687   return m;
    688 }
    689 
    690 inline int power(int a, long long b) {
    691   int res = 1;
    692   while (b > 0) {
    693     if (b & 1) {
    694       res = mul(res, a);
    695     }
    696     a = mul(a, a);
    697     b >>= 1;
    698   }
    699   return res;
    700 }
    701 
    702 inline int inv(int a) {
    703   a %= md;
    704   if (a < 0) a += md;
    705   int b = md, u = 0, v = 1;
    706   while (a) {
    707     int t = b / a;
    708     b -= t * a; swap(a, b);
    709     u -= t * v; swap(u, v);
    710   }
    711   assert(b == 1);
    712   if (u < 0) u += md;
    713   return u;
    714 }
    715 
    716 namespace ntt {
    717   int base = 1;
    718   vector<int> roots = {0, 1};
    719   vector<int> rev = {0, 1};
    720   int max_base = -1;
    721   int root = -1;
    722 
    723   void init() {
    724     int tmp = md - 1;
    725     max_base = 0;
    726     while (tmp % 2 == 0) {
    727       tmp /= 2;
    728       max_base++;
    729     }
    730     root = 2;
    731     while (true) {
    732       if (power(root, 1 << max_base) == 1) {
    733         if (power(root, 1 << (max_base - 1)) != 1) {
    734           break;
    735         }
    736       }
    737       root++;
    738     }
    739   }
    740 
    741   void ensure_base(int nbase) {
    742     if (max_base == -1) {
    743       init();
    744     }
    745     if (nbase <= base) {
    746       return;
    747     }
    748     assert(nbase <= max_base);
    749     rev.resize(1 << nbase);
    750     for (int i = 0; i < (1 << nbase); i++) {
    751       rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
    752     }
    753     roots.resize(1 << nbase);
    754     while (base < nbase) {
    755       int z = power(root, 1 << (max_base - 1 - base));
    756       for (int i = 1 << (base - 1); i < (1 << base); i++) {
    757         roots[i << 1] = roots[i];
    758         roots[(i << 1) + 1] = mul(roots[i], z);
    759       }
    760       base++;
    761     }
    762   }
    763 
    764   void fft(vector<int> &a) {
    765     int n = (int) a.size();
    766     assert((n & (n - 1)) == 0);
    767     int zeros = __builtin_ctz(n);
    768     ensure_base(zeros);
    769     int shift = base - zeros;
    770     for (int i = 0; i < n; i++) {
    771       if (i < (rev[i] >> shift)) {
    772         swap(a[i], a[rev[i] >> shift]);
    773       }
    774     }
    775     for (int k = 1; k < n; k <<= 1) {
    776       for (int i = 0; i < n; i += 2 * k) {
    777         for (int j = 0; j < k; j++) {
    778           int x = a[i + j];
    779           int y = mul(a[i + j + k], roots[j + k]);
    780           a[i + j] = x + y - md;
    781           if (a[i + j] < 0) a[i + j] += md;
    782           a[i + j + k] = x - y + md;
    783           if (a[i + j + k] >= md) a[i + j + k] -= md;
    784         }
    785       }
    786     }
    787   }
    788 
    789   vector<int> multiply(vector<int> a, vector<int> b, int eq = 0) {
    790     int need = (int) (a.size() + b.size() - 1);
    791     int nbase = 0;
    792     while ((1 << nbase) < need) nbase++;
    793     ensure_base(nbase);
    794     int sz = 1 << nbase;
    795     a.resize(sz);
    796     b.resize(sz);
    797     fft(a);
    798     if (eq) b = a; else fft(b);
    799     int inv_sz = inv(sz);
    800     for (int i = 0; i < sz; i++) {
    801       a[i] = mul(mul(a[i], b[i]), inv_sz);
    802     }
    803     reverse(a.begin() + 1, a.end());
    804     fft(a);
    805     a.resize(need);
    806     while (!a.empty() && a.back() == 0) {
    807         a.pop_back();
    808     }
    809     return a;
    810   }
    811 
    812   vector<int> square(vector<int> a) {
    813     return multiply(a, a, 1);
    814   }
    815 };
    816 
    817 const int N = 1e5 + 1;
    818 
    819 vector <vector <int> > polys[N];
    820 int l[N], r[N];
    821 int who[N];
    822 int sz[N];
    823 
    824 vector <int> slozh(const vector <int> &a, const vector <int> &b)
    825 {
    826     int n = (int) a.size(), m = (int) b.size();
    827     vector <int> c(max(n, m));
    828     for (int i = 0; i < n; i++) add(c[i], a[i]);
    829     for (int i = 0; i < m; i++) add(c[i], b[i]);
    830     return c;
    831 }
    832 
    833 pair <vector <int>, vector <int> > eval(const vector <vector <int> > &a)
    834 {
    835     if (a.size() == 1)
    836     {
    837         auto ret = a[0];
    838         ret[0]++;
    839         return {ret, a[0]};
    840     }
    841     else
    842     {
    843         int m = (int) a.size() / 2;
    844         vector <vector <int> > l, r;
    845         for (int i = 0; i < m; i++)
    846         {
    847             l.push_back(a[i]);
    848         }
    849         for (int i = m; i < (int) a.size(); i++)
    850         {
    851             r.push_back(a[i]);
    852         }
    853         auto lf = eval(l), rf = eval(r);
    854         add(lf.first[0], -1);
    855         auto P = slozh(ntt::multiply(lf.first, rf.second), rf.first);
    856         auto Q = ntt::multiply(lf.second, rf.second);
    857         return {P, Q};
    858     }
    859 }
    860 
    861 vector <int> g[N];
    862 
    863 void dfs(int v, int pr)
    864 {
    865     vector <int> go;
    866     int deg = 0;
    867     for (int to : g[v])
    868     {
    869         if (to != pr)
    870         {
    871             go.push_back(to);
    872             deg++;
    873         }
    874     }
    875     if (deg == 0)
    876     {
    877         polys[v].push_back({0, 1});
    878         sz[v] = 1;
    879         who[v] = v;
    880     }
    881     else
    882     {
    883         if (deg == 2)
    884         {
    885             l[v] = go[0];
    886             r[v] = go[1];
    887             dfs(l[v], v);
    888             dfs(r[v], v);
    889             sz[v] = sz[l[v]] + sz[r[v]] + 1;
    890             if (sz[l[v]] < sz[r[v]])
    891             {
    892                 swap(l[v], r[v]);
    893             }
    894             auto go = eval(polys[who[r[v]]]).first;
    895             go.insert(go.begin(), 0);
    896             polys[who[l[v]]].push_back(go);
    897             who[v] = who[l[v]];
    898         }
    899         else
    900         {
    901             int son = go[0];
    902             dfs(son, v);
    903             sz[v] = sz[son] + 1;
    904             who[v] = who[son];
    905             polys[who[v]].push_back({0, 1});
    906         }
    907     }
    908 }
    909 
    910 vector <int> binom(ll n, int k)
    911 {
    912     if (n == 0)
    913     {
    914         vector <int> ret(k + 1);
    915         ret[0] = 1;
    916         return ret;
    917     }
    918     else if (n % 2 == 0)
    919     {
    920         auto a = binom(n / 2, k);
    921         a = ntt::square(a);
    922         a.resize(k + 1);
    923         return a;
    924     }
    925     else
    926     {
    927         auto a = binom(n - 1, k);
    928         for (int i = k; i >= 0; i--)
    929         {
    930             if (i != 0)
    931             {
    932                 add(a[i], a[i - 1]);
    933             }
    934         }
    935         return a;
    936     }
    937 }
    938 
    939 int main()
    940 {
    941 #ifdef ONPC
    942     freopen("a.in", "r", stdin);
    943 #endif
    944     ios::sync_with_stdio(0);
    945     cin.tie(0);
    946     int n;
    947     cin >> n;
    948     ll x;
    949     cin >> x;
    950     vector <int> fact(n + 1), rev_fact(n + 1);
    951     fact[0] = 1;
    952     for (int i = 1; i <= n; i++)
    953     {
    954         fact[i] = mul(fact[i - 1], i);
    955     }
    956     for (int i = 0; i <= n; i++)
    957     {
    958         rev_fact[i] = inv(fact[i]);
    959     }
    960     for (int i = 1; i < n; i++)
    961     {
    962         int a, b;
    963         cin >> a >> b;
    964         a--, b--;
    965         g[a].push_back(b);
    966         g[b].push_back(a);
    967     }
    968     dfs(0, -1);
    969     auto solve = eval(polys[who[0]]).first;
    970     auto big_binoms = binom(x, n);
    971     for (int i = 0; i <= n; i++)
    972     {
    973         big_binoms[i] = mul(big_binoms[i], rev_fact[i]);
    974     }
    975     rev_fact.insert(rev_fact.begin(), 0);
    976     big_binoms = ntt::multiply(big_binoms, rev_fact);
    977     int ans = 0;
    978     for (int i = 1; i <= n; i++)
    979     {
    980         add(ans, mul(mul(solve[i], big_binoms[i]), fact[i - 1]));
    981     }
    982     cout << ans << '\n';
    983 }
    984 ```