提出 #54881518

ソースコード 拡げる

N = gets.to_i
E = Array.new(N){[]}
(N-1).times{
	u,v = gets.split.map{_1.to_i-1}
	E[u]<<v
	E[v]<<u
}
C = gets.split.map(&:to_i)

F = [nil]*N
DCCNS = lambda{|a,p|
	c = C[a]
	dccns = E[a].filter_map{|b| DCCNS[b,a] if b!=p }
	if dccns.empty?
		F[a] = 0
		next 1,{c=>1},{c=>0},1,0
	end
	dccns.sort_by!(&:size)
	f = dccns.sum{|d,cn,cs,n,s|
		cn[c] ? d*cn[c]+cs[c] : 0
	}
	d,cn,cs,n,s = dccns.pop
	dccns.each{|d1,cn1,cs1,n1,s1|
		cn1.each{|c1,nc1|
			sc1 = cs1[c1]
			if nc = cn[c1]
				sc = cs[c1]
				f += (d+d1)*nc*nc1 + sc*nc1 + sc1*nc
			else
				nc = sc = 0
			end
			cn[c1] = nc += nc1
			cs[c1] = sc += sc1+(d1-d)*nc1
		}
		n += n1
		s += s1+(d1-d)*n1
	}
	cn[c] ||= 0
	cn[c] += 1
	cs[c] ||= 0
	cs[c] -= d
	n += 1
	s -= -d
	F[a] = f
	next d+1,cn,cs,n,s
}
DCCNS[0,0]

p F.sum

提出情報

提出日時
問題 G - Sum of Tree Distance
ユーザ ds14050
言語 Ruby (ruby 3.2.2)
得点 0
コード長 825 Byte
結果 TLE
実行時間 4443 ms
メモリ 539276 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 600
結果
AC × 2
AC × 50
TLE × 2
セット名 テストケース
Sample 00_sample_01.txt, 00_sample_02.txt
All 00_sample_01.txt, 00_sample_02.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt, 01_test_37.txt, 01_test_38.txt, 01_test_39.txt, 01_test_40.txt, 01_test_41.txt, 01_test_42.txt, 01_test_43.txt, 01_test_44.txt, 01_test_45.txt, 01_test_46.txt, 01_test_47.txt, 01_test_48.txt, 01_test_49.txt, 01_test_50.txt
ケース名 結果 実行時間 メモリ
00_sample_01.txt AC 43 ms 17096 KiB
00_sample_02.txt AC 43 ms 17220 KiB
01_test_01.txt AC 273 ms 50316 KiB
01_test_02.txt AC 805 ms 121304 KiB
01_test_03.txt AC 1154 ms 154816 KiB
01_test_04.txt AC 290 ms 51288 KiB
01_test_05.txt AC 219 ms 47840 KiB
01_test_06.txt AC 1267 ms 158460 KiB
01_test_07.txt AC 491 ms 80604 KiB
01_test_08.txt AC 1057 ms 145512 KiB
01_test_09.txt AC 1048 ms 142092 KiB
01_test_10.txt AC 1282 ms 195292 KiB
01_test_11.txt AC 1560 ms 201280 KiB
01_test_12.txt AC 1643 ms 201356 KiB
01_test_13.txt TLE 4443 ms 509140 KiB
01_test_14.txt TLE 4439 ms 445292 KiB
01_test_15.txt AC 637 ms 45752 KiB
01_test_16.txt AC 709 ms 59748 KiB
01_test_17.txt AC 652 ms 56280 KiB
01_test_18.txt AC 623 ms 55060 KiB
01_test_19.txt AC 577 ms 52628 KiB
01_test_20.txt AC 621 ms 53068 KiB
01_test_21.txt AC 569 ms 49696 KiB
01_test_22.txt AC 624 ms 50800 KiB
01_test_23.txt AC 929 ms 87492 KiB
01_test_24.txt AC 901 ms 81888 KiB
01_test_25.txt AC 839 ms 66692 KiB
01_test_26.txt AC 564 ms 45172 KiB
01_test_27.txt AC 629 ms 45868 KiB
01_test_28.txt AC 918 ms 68024 KiB
01_test_29.txt AC 1073 ms 125824 KiB
01_test_30.txt AC 1122 ms 110848 KiB
01_test_31.txt AC 2022 ms 517996 KiB
01_test_32.txt AC 2016 ms 517956 KiB
01_test_33.txt AC 2011 ms 517900 KiB
01_test_34.txt AC 2011 ms 517888 KiB
01_test_35.txt AC 569 ms 146884 KiB
01_test_36.txt AC 559 ms 129720 KiB
01_test_37.txt AC 551 ms 130704 KiB
01_test_38.txt AC 538 ms 130180 KiB
01_test_39.txt AC 534 ms 130452 KiB
01_test_40.txt AC 544 ms 130948 KiB
01_test_41.txt AC 2116 ms 539180 KiB
01_test_42.txt AC 2167 ms 539276 KiB
01_test_43.txt AC 2117 ms 529740 KiB
01_test_44.txt AC 2129 ms 530132 KiB
01_test_45.txt AC 1182 ms 160860 KiB
01_test_46.txt AC 1086 ms 121692 KiB
01_test_47.txt AC 1031 ms 107696 KiB
01_test_48.txt AC 968 ms 91036 KiB
01_test_49.txt AC 1503 ms 184720 KiB
01_test_50.txt AC 1231 ms 145780 KiB