Submission #59386639

---

Source Code Expand

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

P = 0,1,[nil]*(N-1) # 1 は根
親決め = lambda{|v,p|
	P[v] = p
	E[v].each{|c|
		親決め[c,v] if c!=p
	}
}
親決め[1,1]

a = 0
３の下にいる２の数 = [0]*(N+1)
D = E.map(&:size)
Q = (2..N).select{|v| D[v]==1 } # 葉
while v = Q.shift
	p = P[v]
	d = E[v].size
	if d==3
		sum = 0
		E[v].each{|c|
			next if c==p
			cd = ３の下にいる２の数[c]
			a += sum*cd
			sum += cd
		}
		３の下にいる２の数[v] = sum
	elsif d==2
		E[v].each{|c|
			next if c==p
			a += ３の下にいる２の数[c] if E[c].size==3
		}
		３の下にいる２の数[v] = 1
	end
	Q<<p if 1==D[p] -= 1
end

p a

Submission Info

Judge Result