Submission #50189012

Source Code Expand

P = 998244353
N = gets.to_i
A = gets.split.map(&:to_i)
E = Array.new(N){{}}
(N-1).times{
	u,v = gets.split.map{_1.to_i-1}
	E[u][v] = v
	E[v][u] = u
}
if N<2
	p 1
	exit
end

X = [nil]*N
C = Array.new(N){[]}
Q = N.times.select{|a| E[a].size==1 }
while u = Q.shift
	v, = E[u].shift
	X[u] = C[u].sum{|a2t| a2t[A[u]] }
	C[u].sort_by!(&:size)
	a2t = C[u].pop||Hash.new(0)
	C[u].each{|_|
		_.each{|a,t|
			a2t[a] = ((a2t[a]+1)*(t+1)-1)%P
		}
	}.clear
	a2t[A[u]] += 1
	break unless v
	C[v]<<a2t
	E[v].delete u
	Q<<v if E[v].size==1
end

p (X.sum+a2t.values.sum)%P

Submission Info

Submission Time
Task G - Leaf Color
User ds14050
Language Ruby (ruby 3.2.2)
Score 600
Code Size 591 Byte
Status AC
Exec Time 1023 ms
Memory 127188 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 55
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 01_small_06.txt, 01_small_07.txt, 01_small_08.txt, 01_small_09.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt, 02_random_21.txt, 02_random_22.txt, 02_random_23.txt, 02_random_24.txt, 02_random_25.txt, 02_random_26.txt, 02_random_27.txt, 02_random_28.txt, 02_random_29.txt, 03_star_00.txt, 03_star_01.txt, 03_star_02.txt, 03_star_03.txt, 03_star_04.txt, 04_path_00.txt, 04_path_01.txt, 04_path_02.txt, 04_path_03.txt, 04_path_04.txt, 05_corner_00.txt, 05_corner_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 133 ms 17212 KiB
00_sample_01.txt AC 46 ms 17108 KiB
00_sample_02.txt AC 46 ms 17284 KiB
01_small_00.txt AC 46 ms 17220 KiB
01_small_01.txt AC 46 ms 17272 KiB
01_small_02.txt AC 45 ms 16796 KiB
01_small_03.txt AC 46 ms 17200 KiB
01_small_04.txt AC 46 ms 17232 KiB
01_small_05.txt AC 47 ms 17044 KiB
01_small_06.txt AC 45 ms 17124 KiB
01_small_07.txt AC 46 ms 17080 KiB
01_small_08.txt AC 47 ms 17232 KiB
01_small_09.txt AC 45 ms 16920 KiB
02_random_00.txt AC 571 ms 72820 KiB
02_random_01.txt AC 983 ms 111036 KiB
02_random_02.txt AC 990 ms 112100 KiB
02_random_03.txt AC 986 ms 109756 KiB
02_random_04.txt AC 522 ms 68936 KiB
02_random_05.txt AC 939 ms 96308 KiB
02_random_06.txt AC 979 ms 110824 KiB
02_random_07.txt AC 948 ms 101784 KiB
02_random_08.txt AC 762 ms 89980 KiB
02_random_09.txt AC 890 ms 92552 KiB
02_random_10.txt AC 999 ms 112368 KiB
02_random_11.txt AC 958 ms 102452 KiB
02_random_12.txt AC 145 ms 30388 KiB
02_random_13.txt AC 959 ms 102460 KiB
02_random_14.txt AC 1007 ms 119932 KiB
02_random_15.txt AC 995 ms 111452 KiB
02_random_16.txt AC 832 ms 95672 KiB
02_random_17.txt AC 1023 ms 127188 KiB
02_random_18.txt AC 905 ms 92444 KiB
02_random_19.txt AC 983 ms 111600 KiB
02_random_20.txt AC 128 ms 30236 KiB
02_random_21.txt AC 907 ms 92512 KiB
02_random_22.txt AC 883 ms 92552 KiB
02_random_23.txt AC 947 ms 100808 KiB
02_random_24.txt AC 270 ms 42388 KiB
02_random_25.txt AC 933 ms 99616 KiB
02_random_26.txt AC 957 ms 102932 KiB
02_random_27.txt AC 919 ms 95620 KiB
02_random_28.txt AC 141 ms 31088 KiB
02_random_29.txt AC 989 ms 111660 KiB
03_star_00.txt AC 826 ms 125800 KiB
03_star_01.txt AC 841 ms 126592 KiB
03_star_02.txt AC 844 ms 126152 KiB
03_star_03.txt AC 847 ms 125968 KiB
03_star_04.txt AC 832 ms 125996 KiB
04_path_00.txt AC 503 ms 79520 KiB
04_path_01.txt AC 738 ms 84200 KiB
04_path_02.txt AC 515 ms 80460 KiB
04_path_03.txt AC 698 ms 81120 KiB
04_path_04.txt AC 507 ms 79844 KiB
05_corner_00.txt AC 576 ms 92424 KiB
05_corner_01.txt AC 827 ms 126060 KiB