Submission #49587091

---

Source Code Expand

class BIT
	def initialize n
		@a = [0]*(n+1) # 1-indexed internally
	end

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end

	def add i,d
		i += 1
		while i<@a.size
			@a[i] += d
			i += i&-i
		end
	end
	def inc i; add i,1 end
end

N = gets.to_i
P = [0]+[nil]*N
Dn = BIT.new N+1
DnC = Array.new(N+1){{}}
DnSum = [0]*(N+1)
(N-1).times{
	u,v = gets.split.map(&:to_i)
	DnC[u][v] = v
	DnC[v][u] = u
}
F = lambda{|v,p|
	P[v] = p
	cs = DnC[v]
	dnp = v-1
	cs.transform_values!{|c|
		next if c==p
		dnc = Dn[v]
		F[c,v]
		dnc = Dn[v]-dnc
		DnSum[v] += dnc+DnSum[c]
		dnp -= dnc
		next dnc
	}
	cs[p] = dnp
	Dn.inc v
}
G = lambda{|v,dnsump|
	p = P[v]
	DnSum[v] += DnC[v][p]+dnsump
	DnC[v].each{|c,dnc|
		G[c,DnSum[v]-dnc-DnSum[c]] if c!=p
	}
}

F[1,0]
G[1,0]

puts DnSum[1,N]*' '

Submission Info

Judge Result