Submission #68969535

---

Source Code Expand

Q = gets.to_i
C = Array.new(Q+1){[]}
Qry = (1..Q).map{|q|
	_,x,y = gets.split.map(&:to_i)
	C[x]<<q unless y
	next q,x,y
}
I = [nil]*(Q+1) # x,y の順序
F = lambda{|i,x;c|
	I[x] = i += 1
	cs = C[x]
	i = F[i,c] while c = cs.pop
	i
}
F[0,0]

A = []
Nx = [nil]*(Q+1)
while (q,x,y = Qry.shift)
	if y
		x,y = y,x if I[y]<I[x]
		s = 0
		nx = Nx[x]
		Nx[x] = y
		until nx==y
			s += nx
			nx = Nx[nx]
		end
		A<<s
	else
		# x -> q -> Nx[x]
		Nx[q] = Nx[x]
		Nx[x] = q
	end
end
puts A

Submission Info

Judge Result