QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#457262#439. 命运Naganohara_Yoimiya100 ✓1690ms455832kbC++143.7kb2024-06-29 09:48:162024-06-29 09:48:18

Judging History

你现在查看的是最新测评结果

  • [2024-06-29 09:48:18]
  • 评测
  • 测评结果:100
  • 用时:1690ms
  • 内存:455832kb
  • [2024-06-29 09:48:16]
  • 提交

answer

//-DYUNQIAN -std=c++14 -O2 -Wl
#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}

void Assert(bool c,int L=0){if(!c){cout<<"Assertion Failed at "<<L<<endl;exit(0);}}

const int N=5e5+5;
vector<int>G[N];
int M[N],n,dep[N],m;

int sum[N];
void dfs(int u,int fa){for(int v:G[u])if(v!=fa)dep[v]=dep[u]+1,dfs(v,u);}

struct F{int cv,ml,ad;F(int C=0,int M=0,int A=0):cv(C),ml(M),ad(A){}};
bool operator==(F x,F y){return x.cv==y.cv&&x.ad==y.ad&&x.ml==y.ml;}
bool operator!=(F x,F y){return !(x==y);}
int OUT=0,MERGE=0;
struct SegTree{
	int d[N<<5];F lz[N<<5];int tot=0,cnt=0,b[N<<5],ls[N<<5],rs[N<<5];
	
	int e(){return 0;}
	F ef(){return F(-1,1,0);}
	//cov , mul , add
	
	int build(){
		int p=(cnt==0?++tot:b[cnt--]);
		ls[p]=rs[p]=0,d[p]=e(),lz[p]=ef();
		return p;
	}
	void del(int p){
		ls[p]=rs[p]=d[p]=0,lz[p]=ef();
		b[++cnt]=p;
	}
	
	int op(int x,int y){return (x+y>=mod?x+y-mod:x+y);}
	F comp(F f,F g){// f(g(x))
		if(f.cv!=-1)return f;
		if(g.cv!=-1)return F(op(1ll*op(1ll*g.cv*g.ml%mod,g.ad)*f.ml%mod,f.ad),1,0);
		else return F(-1,1ll*g.ml*f.ml%mod,op(1ll*f.ml*g.ad%mod,f.ad));
	}
	void app(F f,int p){
		if(f.cv!=-1)d[p]=f.cv;
		d[p]=op(1ll*d[p]*f.ml%mod,f.ad);
		lz[p]=comp(f,lz[p]);
	}
	
	#define ls(p) (ls[p])
	#define rs(p) (rs[p])
	void pushup(int p){d[p]=max(d[ls(p)],d[rs(p)]);}
	void pushdown(int p){
		if(lz[p]==ef())return ;
		if(!ls(p))ls(p)=build();
		if(!rs(p))rs(p)=build();
		app(lz[p],ls(p)),app(lz[p],rs(p));
		lz[p]=ef();
	}
	
	void Mul(int l,int r,F f,int ql,int qr,int &p){
		if(!p)p=build();
		if(l<=ql&&qr<=r){app(f,p);return ;}
		int mid=(ql+qr)>>1;pushdown(p);
		if(l<=mid)Mul(l,r,f,ql,mid,ls(p));
		if(r>mid)Mul(l,r,f,mid+1,qr,rs(p));
		pushup(p);
	}
	int qval(int x,int ql,int qr,int p){
		if(!p)return 0;
		if(ql==qr)return d[p];
		int mid=(ql+qr)>>1;pushdown(p);
		if(x<=mid)return qval(x,ql,mid,ls(p));
		else return qval(x,mid+1,qr,rs(p));
	}
	
	int merge(int p,int q,int l,int r){
		if(!p||!q)return p+q;
		if(l==r){d[p]=1ll*d[p]*d[q]%mod,del(q);return p;}
		if(((!ls(p))&&(!rs(p)))||((!ls(q))&&(!rs(q)))){
			if(ls(q)||rs(q))swap(p,q);
			int rval=0;
			if(lz[q].cv!=-1)rval=op(1ll*lz[q].cv*lz[q].ml%mod,lz[q].ad);
			else rval=lz[q].ad;
			app(F(-1,rval,0),p),del(q);return p;
		}
		int mid=(l+r)>>1;
		pushdown(p),pushdown(q);
		ls[p]=merge(ls(p),ls(q),l,mid),rs[p]=merge(rs(p),rs(q),mid+1,r);
		pushup(p);del(q);return p;
	}
}T;

int root[N];

void Mul(int l,int r,F f,int u){
	l++,r++;if(l>r)return ;
	T.Mul(l,r,f,1,n,root[u]);
}
int Qval(int v,int u){
	v++;
	return T.qval(v,1,n,root[u]);
}

void DP(int u,int fa){
	Mul(M[u],dep[u]-1,F(1,1,0),u);
	for(int v:G[u]){
		if(v==fa)continue;DP(v,u);
		root[u]=T.merge(root[u],root[v],1,n);
	}
	if(u==1)return ;
	int val=Qval(dep[u]-1,u);
	Mul(dep[u],n-1,F(0,1,0),u),Mul(0,M[u]-1,F(0,1,0),u),Mul(0,dep[u]-1,F(-1,1,val),u);
}

signed main(void){

	n=read();
	for(int i=2;i<=n;i++){
		int x=read(),y=read();
		G[x].emplace_back(y),G[y].emplace_back(x);
	}
	dep[1]=1;dfs(1,0);
	m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		M[v]=max(M[v],dep[u]);
	}
	DP(1,0);cout<<Qval(0,1)<<endl;;

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4
Accepted
time: 19ms
memory: 214024kb

input:

6
2 3
6 5
6 4
6 1
2 4
7
1 2
4 2
1 6
2 3
6 5
6 2
6 2

output:

2

result:

ok answer is '2'

Test #2:

score: 4
Accepted
time: 28ms
memory: 217796kb

input:

7
6 4
3 6
3 2
3 7
1 4
5 7
9
1 2
1 5
1 7
1 5
1 4
6 2
3 7
4 3
3 2

output:

6

result:

ok answer is '6'

Test #3:

score: 4
Accepted
time: 11ms
memory: 216776kb

input:

8
6 8
7 6
6 1
6 5
2 8
4 6
6 3
8
6 7
6 8
1 6
6 8
8 2
6 7
1 5
1 6

output:

8

result:

ok answer is '8'

Test #4:

score: 4
Accepted
time: 8ms
memory: 213952kb

input:

9
6 4
1 7
1 3
4 8
2 7
5 1
1 4
9 4
10
1 5
1 9
4 9
1 5
1 4
1 8
1 5
1 2
1 2
1 2

output:

24

result:

ok answer is '24'

Test #5:

score: 4
Accepted
time: 4ms
memory: 216960kb

input:

497
255 412
294 262
337 292
138 17
74 260
134 344
453 364
114 289
50 280
360 179
51 433
497 438
490 422
99 119
345 318
259 396
298 272
431 37
38 15
101 213
230 195
193 33
126 307
106 170
24 200
245 367
266 75
275 67
405 432
220 331
411 441
452 479
219 16
410 245
219 312
476 424
104 356
144 230
251 2...

output:

913693353

result:

ok answer is '913693353'

Test #6:

score: 4
Accepted
time: 20ms
memory: 214836kb

input:

10000
2286 4570
6005 8498
6796 7409
8543 5599
5964 3049
9689 64
555 8795
8719 1929
5814 6317
7104 2223
5537 4410
150 1311
9975 2583
8069 5198
6516 9798
7906 2340
9867 3843
1566 6050
4261 1981
6603 9122
7172 6996
9675 5124
6680 9947
920 1437
6693 4264
4977 7255
3707 2622
9914 4090
588 3714
147 7574
8...

output:

741099208

result:

ok answer is '741099208'

Test #7:

score: 4
Accepted
time: 168ms
memory: 226064kb

input:

99999
24827 62592
58601 32988
9374 5313
16621 75518
13429 72361
72162 10410
19352 43426
50088 85249
60117 54428
45780 95257
71828 69234
45367 69122
8537 31711
19060 14175
49101 29413
77638 37540
14341 97505
86792 56691
24399 74996
48465 6197
84803 31855
79897 68879
43215 30590
32130 9225
41151 5727
...

output:

298377224

result:

ok answer is '298377224'

Test #8:

score: 4
Accepted
time: 1081ms
memory: 288188kb

input:

500000
481001 130369
33906 415753
490524 96079
164735 455776
70736 279997
378857 446203
146479 379023
277575 479123
279016 452847
157934 276420
365178 355559
92278 334178
384516 170203
53281 287053
91013 116371
66198 157826
439312 51593
299436 230757
87865 296922
14619 361816
196065 266068
333188 40...

output:

620543783

result:

ok answer is '620543783'

Test #9:

score: 4
Accepted
time: 178ms
memory: 225872kb

input:

99997
12420 85497
96299 96503
91359 61879
73963 53821
8421 57985
20625 76112
7710 49712
37822 48930
73283 21602
95544 63863
48109 71430
71156 13272
94319 85892
44636 21771
13012 32434
25568 67705
2402 72273
45184 77931
47042 90239
24095 8125
28880 6901
53229 34081
99484 60358
11889 94257
40320 63099...

output:

76263105

result:

ok answer is '76263105'

Test #10:

score: 4
Accepted
time: 1056ms
memory: 282688kb

input:

499997
30888 482221
413340 184626
407235 423912
444162 164665
292046 377512
92865 497459
295659 434257
373183 130281
274974 165820
417090 329358
457165 135108
364466 306280
481928 272283
203252 229766
184132 104900
1319 197293
95369 415252
423790 88530
453001 268063
55065 23949
434123 184247
239979 ...

output:

495702396

result:

ok answer is '495702396'

Test #11:

score: 4
Accepted
time: 12ms
memory: 217872kb

input:

598
495 238
121 55
369 328
139 276
230 262
309 232
357 183
521 350
177 193
557 336
214 12
285 13
137 36
353 208
81 470
361 583
226 418
88 364
280 252
428 338
216 142
35 584
62 326
27 594
151 6
425 339
159 464
209 224
598 294
312 90
466 185
108 374
253 379
524 289
389 458
78 446
332 319
511 21
468 16...

output:

422402046

result:

ok answer is '422402046'

Test #12:

score: 4
Accepted
time: 14ms
memory: 214144kb

input:

999
634 560
72 10
17 369
466 932
424 205
200 457
53 37
252 64
866 450
669 985
607 667
30 584
733 678
666 10
450 328
375 924
283 189
948 327
665 700
831 267
315 305
117 352
201 929
704 672
10 51
450 868
966 978
540 76
275 15
35 398
405 109
395 92
327 146
411 135
10 972
10 917
623 600
719 123
208 370
...

output:

426197544

result:

ok answer is '426197544'

Test #13:

score: 4
Accepted
time: 41ms
memory: 215116kb

input:

1998
1129 982
64 915
984 1123
606 220
1624 1776
401 1840
159 370
1733 1699
753 317
559 1096
1443 152
1678 682
1033 1153
1745 350
1908 325
618 454
194 1195
786 1254
950 912
784 1582
333 910
32 279
1818 823
1426 990
1863 1182
1428 1526
1113 373
884 609
1113 270
1094 391
405 1440
784 959
998 1509
205 1...

output:

259778043

result:

ok answer is '259778043'

Test #14:

score: 4
Accepted
time: 22ms
memory: 214648kb

input:

1999
1039 956
987 1079
113 930
1411 1611
99 1121
115 1379
1811 835
855 44
78 378
833 1317
1642 841
1012 1411
1504 841
588 851
1565 1811
1411 1687
361 1712
1538 1411
819 584
477 1146
1014 1268
1956 366
430 287
1043 1294
910 1413
676 16
1024 1027
1915 841
1411 178
1399 1185
1937 158
1397 841
68 249
13...

output:

719079531

result:

ok answer is '719079531'

Test #15:

score: 4
Accepted
time: 1042ms
memory: 346164kb

input:

499996
166429 374240
458250 186205
337525 397040
105532 121824
323632 293915
266697 417228
180442 297190
79265 219324
80328 16227
130791 321970
91028 57527
42303 425087
297432 223699
311644 18598
155816 2585
280416 329400
38048 413818
353672 18723
460086 20894
376884 401233
273015 96291
64286 98896
...

output:

440462992

result:

ok answer is '440462992'

Test #16:

score: 4
Accepted
time: 1093ms
memory: 382560kb

input:

499999
429752 39010
87476 462988
436786 265632
313093 371847
150379 79799
292525 421113
461636 397528
468254 298152
329871 294594
374787 213141
349056 299400
157824 375747
127664 310858
51614 316107
247619 483715
99405 317027
451439 413890
271303 104915
14174 237451
72169 43889
267943 170586
111172 ...

output:

503694719

result:

ok answer is '503694719'

Test #17:

score: 4
Accepted
time: 107ms
memory: 218032kb

input:

99997
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27...

output:

951546685

result:

ok answer is '951546685'

Test #18:

score: 4
Accepted
time: 108ms
memory: 217956kb

input:

100000
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

398299966

result:

ok answer is '398299966'

Test #19:

score: 4
Accepted
time: 133ms
memory: 239592kb

input:

49994
16773 18084
13652 26028
29320 22500
8168 20391
20712 13289
18306 48732
1147 32403
22074 29376
42713 11128
26847 2494
20937 3907
44148 35349
27897 4800
7299 31995
33721 5113
31418 10206
19747 35922
10414 25963
18776 42084
44938 6516
4800 5329
41176 17864
31066 12752
29923 33698
47504 37268
4724...

output:

311193151

result:

ok answer is '311193151'

Test #20:

score: 4
Accepted
time: 219ms
memory: 251484kb

input:

79998
15767 34291
71245 14457
74445 58864
16367 6779
48359 64486
19508 48504
62217 20603
37223 443
59509 35966
38405 16920
79413 77556
27559 51976
66736 3647
41686 52728
46231 43331
34940 36057
61287 64199
76627 37116
21332 78604
27326 78434
58838 67326
24178 59289
10708 15944
14521 15352
23285 2543...

output:

108272378

result:

ok answer is '108272378'

Test #21:

score: 4
Accepted
time: 282ms
memory: 241684kb

input:

99999
14680 98099
68941 56143
16160 83923
32354 64072
19605 7048
24721 7369
32025 33248
57959 42630
48493 52559
48493 15160
76901 41756
31947 88634
98862 48493
70561 81999
81064 6357
29348 88172
36474 76470
70131 49915
12930 22381
25437 70561
70561 56236
70561 43957
17512 54072
48987 9540
42841 2154...

output:

38247969

result:

ok answer is '38247969'

Test #22:

score: 4
Accepted
time: 271ms
memory: 251016kb

input:

99996
81219 46611
27070 96230
88963 28320
47132 90466
47025 55027
56136 29854
12528 51209
51703 49946
85094 23069
28768 29508
51373 56376
21628 27271
75141 74333
86616 42671
47071 81610
71794 38614
95689 68213
21472 76729
95826 1
7067 56421
9255 1
46816 26963
68196 56713
83546 84190
92874 63215
4799...

output:

881239389

result:

ok answer is '881239389'

Test #23:

score: 4
Accepted
time: 1397ms
memory: 358892kb

input:

499999
328444 232129
34137 337939
1 2770
145619 337672
223675 257443
252889 184274
435369 80009
390302 338638
87899 38243
328444 374192
95368 379319
203463 293410
158770 373327
153849 111860
303903 481356
129222 216039
287062 175092
485781 979
359098 421597
5354 229733
227881 30640
142194 126688
344...

output:

213231046

result:

ok answer is '213231046'

Test #24:

score: 4
Accepted
time: 1690ms
memory: 455832kb

input:

499996
234812 237052
231031 104664
102145 299812
273901 51367
487834 495839
77385 276903
393563 119918
136245 318870
68288 88488
185218 237190
347758 398936
492387 460746
287846 454723
400936 222847
77067 485362
113343 113127
25637 124859
146819 460819
118564 204986
1597 420874
406709 470358
318130 ...

output:

775170

result:

ok answer is '775170'

Test #25:

score: 4
Accepted
time: 1246ms
memory: 329512kb

input:

499999
413164 1
45178 10034
77624 1
1 295033
113198 162474
5742 45178
76083 379306
271416 134250
130336 491344
426378 1
10340 45178
14040 430225
1 468965
210040 482376
22963 473681
173835 464785
73841 103763
209733 383125
469692 1
1 14003
375214 363310
45178 208777
16359 260731
340784 490818
491344 ...

output:

247536705

result:

ok answer is '247536705'

Extra Test:

score: 0
Extra Test Passed