QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#437815 | #4012. 深搜 | Williamxzh | 0 | 180ms | 43964kb | C++23 | 3.4kb | 2024-06-09 18:00:05 | 2024-06-09 18:00:05 |
Judging History
answer
#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
const ll mod=998244353;
il ll qp(ll a,ll b){
ll ans=1ll;a%=mod;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod,b>>=1;
}return ans;
}
il int read(){
int x=0,c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-48,c=getchar();
return x;
}
const int N=4e5+5;
int T,n,rt,a[N],fa[N],de[N],ck1,ck2,in[N],id[N],b[N];ll ans,fac[N],inv[N];
int st[N],top,l[N],r[N];
vector<int> e[N];
il void adde(int x,int y){e[x].push_back(y);}
void dfs(int x,int fath){
}
il void init(){
for(int i=1;i<=n;++i) a[i]=fa[i]=de[i]=in[i]=0,e[i].clear();
ck1=ck2=1;
fac[0]=1ll;for(int i=1;i<=n;++i) fac[i]=(fac[i-1]*1ll*i)%mod;
inv[n]=qp(fac[n],mod-2ll);for(int i=n-1;i>=0;--i) inv[i]=(inv[i+1]*(i+1ll))%mod;
}
il ll C(int n,int m){return (fac[n]*inv[m]%mod*inv[n-m])%mod;}
int x,y,z;ll u,v,w;int p[N];
int main(){
//freopen("c1.in","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&rt);init(),ans=0ll;
for(int i=1;i<=n;++i) a[i]=read();
for(int i=2;i<=n;++i) x=read(),y=read(),adde(x,y),adde(y,x);
for(int i=1;i<=n;++i) ck1&=(e[i].size()<=2);
ck1&=(n==1 || e[rt].size()==1),ck2=(e[rt].size()==n-1);
if(ck1){
top=0;
for(int i=1;i<=n;++i){
while(top && a[st[top]]>a[i]) --top;
l[i]=(top?st[top]+1:1),st[++top]=i;
}top=0;
for(int i=n;i;--i){
while(top && a[st[top]]>=a[i]) --top;
r[i]=(top?st[top]-1:n),st[++top]=i;
}top=0;
for(int i=1;i<=n;++i){
ans=(ans+(i-l[i]+1ll)*(r[i]-i+1ll)%mod*a[i])%mod;
}
printf("%lld\n",ans);continue;
}
if(ck2){
for(int i=1;i<=n;++i) id[i]=i;
sort(id+1,id+1+n,[](int x,int y){return a[x]==a[y]?x<y:a[x]<a[y];});
for(int i=1;i<=n;++i) b[id[i]]=i;
x=0;for(int i=1;i<=n;++i) if(i!=rt) id[++x]=i;
sort(id+1,id+n,[](int x,int y){return a[x]==a[y]?x<y:a[x]<a[y];});
for(int i=1;i<n;++i){
x=id[i];if(b[x]>b[rt]) break;
if(i==n-1) break;
u=0ll;
for(int j=0;j<=n-2-i;++j){
u=(u+C(n-2-i,j)*fac[j+1]*fac[n-j-3])%mod;
}
ans=(ans+u*(n-i-1ll)%mod*a[x])%mod;
}
for(int i=1;i<n;++i){
x=id[i];if(b[x]<b[rt]) continue;
ans=(ans+1ll*a[rt]*(n-i)%mod*fac[n-i]%mod*fac[i-1])%mod;
break;
//for(int j=0;j<=n;++j) ;
}
for(int i=1;i<n;++i){
x=id[i];if(b[x]>b[rt]) break;
ans=(ans+1ll*a[x]*fac[n-i]*fac[i-1])%mod;
}
w=0;
for(int i=1;i<n;++i) p[i]=i;
do{
x=a[rt];
for(int i=1;i<n;++i) x=min(x,a[id[p[i]]]),w+=1ll*x;
}while(next_permutation(p+1,p+n));
//printf("%lld\n",w);
//printf("%lld\n",ans);
ans=(ans*inv[n-1])%mod;
for(int i=1;i<=n;++i) ans+=1ll*a[i];ans%=mod;
printf("%lld\n",ans);continue;
}
dfs(rt,0);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 16000kb
input:
4 10 1 27435958 783263696 41066275 980665324 159051035 354302521 186596867 419160808 237766864 555242451 3 1 5 1 7 1 6 3 2 3 9 3 8 6 10 5 4 6 10 3 286818263 522276935 662342351 12293873 518124145 94513580 572539758 1534314 761363637 269173754 3 6 8 6 4 3 2 4 1 2 9 3 7 2 5 2 10 3 10 4 17672277 739368...
output:
result:
wrong answer Answer contains longer sequence [length = 4], but output contains 0 elements
Test #2:
score: 0
Wrong Answer
time: 6ms
memory: 16456kb
input:
7 5000 933 23306350 162661794 68618194 666430282 995855733 929210414 295740530 464135554 304211641 725090719 226242817 592655639 936895997 479520010 108891341 598601399 678169271 118406229 394867734 640888099 481066130 606481085 709600400 554804145 179044332 41718098 549318629 400214219 159098456 67...
output:
result:
wrong answer Answer contains longer sequence [length = 7], but output contains 0 elements
Test #3:
score: 0
Wrong Answer
time: 3ms
memory: 16424kb
input:
7 5000 3103 370388267 486433577 320921400 202742370 718520472 895122554 359601184 337298427 146232648 830940586 826047977 229951976 919497287 67059290 843962706 777524684 196246825 682863698 122309598 743014832 349595264 964812795 660215381 963691135 376209511 759526115 822829377 916639371 802105594...
output:
result:
wrong answer Answer contains longer sequence [length = 7], but output contains 0 elements
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 16336kb
input:
7 5000 4968 717470184 105172657 308383390 593830267 706026427 861034695 423461838 60718197 988253654 231757749 690694353 162215609 461907090 804341675 874001367 811223777 714324378 97578063 704527271 140108861 363348590 28177209 760573466 522321229 868341986 917525621 541050526 287840331 295369628 8...
output:
result:
wrong answer Answer contains longer sequence [length = 7], but output contains 0 elements
Test #5:
score: 0
Wrong Answer
time: 44ms
memory: 22272kb
input:
6 100000 64523 754457004 816672702 108228103 727565046 575355672 557029941 374900316 667662208 247774859 241366803 327704349 984466565 870042639 983615018 950320614 473363640 338609139 877917484 271995097 819820270 213958988 431503923 943718683 511580322 791201903 944289849 290330452 148342386 88563...
output:
result:
wrong answer Answer contains longer sequence [length = 6], but output contains 0 elements
Test #6:
score: 0
Wrong Answer
time: 44ms
memory: 24232kb
input:
6 100000 27972 828633097 164239555 181485176 220605565 677776542 945405871 80032153 66332854 697109172 781941604 919689741 375235146 744974712 849606202 656187811 476076039 737032058 914423438 292449741 668723961 67722543 681470786 510488095 55665910 324786541 329651259 397950166 495275796 250945521...
output:
result:
wrong answer Answer contains longer sequence [length = 6], but output contains 0 elements
Test #7:
score: 0
Wrong Answer
time: 47ms
memory: 22368kb
input:
6 100000 99053 836797137 52289738 16685232 129865475 495829444 97013519 944813587 482856253 783712967 280370957 362687061 720487922 790405858 101237849 24038113 444097770 473476096 758876685 251305540 540743087 490978674 937704773 452442801 129907216 995115116 2093475 885869693 97229474 78775431 917...
output:
result:
wrong answer Answer contains longer sequence [length = 6], but output contains 0 elements
Test #8:
score: 0
Wrong Answer
time: 46ms
memory: 24304kb
input:
6 100000 83118 237932086 805355107 875130961 45785348 463436298 235970586 792133756 802382318 612808476 551682021 372485130 452790514 513627049 543295307 217598321 265929567 797044227 688393222 126744189 35928058 811269903 849584261 483513038 911837564 366458567 951847531 105866839 756251409 4968014...
output:
result:
wrong answer Answer contains longer sequence [length = 6], but output contains 0 elements
Test #9:
score: 0
Wrong Answer
time: 45ms
memory: 24424kb
input:
6 100000 10574 960703914 919137270 287906775 779918168 386941712 826368624 487253993 514726858 887984890 319651075 169632006 397669774 306766175 855993268 923893384 657564124 709799196 903310348 199644397 525583279 671731311 208189848 589129815 666199622 43201407 53804137 209640204 481408933 8963734...
output:
result:
wrong answer Answer contains longer sequence [length = 6], but output contains 0 elements
Test #10:
score: 0
Wrong Answer
time: 40ms
memory: 24240kb
input:
6 100000 47654 766386374 205079444 260272024 972278825 717481371 349976769 283239755 15665182 300195285 987350791 13544206 466113372 892906150 988276842 194045085 558067840 335484149 509185986 186108072 274113084 111042012 993726778 61868884 324431830 214676266 481275089 711334587 593870246 66804272...
output:
result:
wrong answer Answer contains longer sequence [length = 6], but output contains 0 elements
Test #11:
score: 0
Wrong Answer
time: 180ms
memory: 43336kb
input:
2 400000 73762 862365565 233904902 801015102 662519031 634410644 227172052 743137547 514055616 901427716 333289732 679283877 568568098 821858064 900217898 250453718 239331147 531665581 594636716 707168609 243610236 780894216 387870279 57816953 665974155 852470526 447162507 984329800 324745826 648826...
output:
result:
wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements
Test #12:
score: 0
Wrong Answer
time: 149ms
memory: 43964kb
input:
2 400000 180730 283679 983620135 419033314 274303 343530 308182712 375822 45406021 366954 399008 366633 837674994 329650 360017 288950 277451 203169793 385005 316914 389300 303322 286932 439917459 687266506 764762746 449043978 391165 311270 380013 393169 345981033 910239308 380646924 299464 361992 3...
output:
561057767 955665279
result:
wrong answer 1st numbers differ - expected: '67238765', found: '561057767'
Test #13:
score: 0
Time Limit Exceeded
input:
2 400000 309765 608775667 2131331 19559078 184012043 685615762 442328255 931612136 529256531 935758543 341964692 231753076 488819352 562178404 147253046 455118877 266114488 858190561 917679823 291148237 543342791 440565290 435206139 525542915 264075402 333530359 457791306 489112656 108324348 2636130...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
8 400000 118685 563038117 164859136 875514816 414577137 207063568 180641868 6858550 670584198 840248854 719916627 355334822 261100963 744471049 179701455 495589851 965109007 541879502 93191727 882197621 358481538 776798303 217800726 735690344 593562409 596151883 961008602 276219514 953242403 4520340...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
8 400000 56831 39305072 737148944 336185731 716119446 760337621 655681744 542372269 750217715 62681530 834573986 860212279 521396405 688870985 637821243 976200106 132892098 909483916 473083861 16875959 571143365 33780 856724396 477673390 794820014 861346773 806613122 477361925 475474224 692074471 90...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
8 400000 271400 527447986 360811427 317017664 684828353 391380009 542327695 267322015 586422324 889511216 854834175 632621931 900169642 664163528 820142562 222838473 779439110 603516252 215557423 829632387 757052272 697974326 75296094 8469383 359552466 883582471 555120109 121218152 349025115 4932437...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
8 400000 204296 806628574 273742974 866712437 226998068 642801806 22383765 753271715 674756473 299387492 209571507 751275793 919256451 337786380 491580239 159416489 764391570 951432009 713509140 903817894 993064795 905131631 384653665 20803351 610020998 295650025 774016199 674028639 680000304 529944...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
8 400000 353099 879456874 557757894 400986897 727818310 693419201 397437153 726864591 799191577 659112264 630450084 689653945 382288990 787889994 481730943 427157777 238933264 565465508 473760154 621744880 838839073 82035016 619039056 674700480 54834933 377602492 68062382 703511235 592317668 5296147...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
8 400000 313260 790289117 748491080 399039629 237539968 91489408 394990092 628685615 218246466 863553504 839507705 373074016 738615388 659048944 791174911 277956988 891328055 782764818 997830053 710026897 726956820 193562016 208122244 776709858 489677702 473778791 318354634 962748261 229609206 53136...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
8 400000 193563 599165056 664142718 3384356 11687180 279533263 281721841 264845580 883884612 299413775 173831631 362304213 124607691 339027082 706284781 292193066 522444453 222655337 218716836 432347863 530915231 565605183 933368403 51262544 543200200 506551679 449461720 47099435 733008370 736941569...