Submission #52760322

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
P = 998244353
N = gets.to_i
G = [-1]*N
E = [0]*N
F = lambda{|a|
  next a if G[a]<0
  ra = G[a]
  G[a] = F[ra]
  E[a] += E[ra] if ra!=G[a]
  next G[a]
}
U = lambda{|a,b|
  ra,rb = F[a],F[b]
  za,zb = -G[ra],-G[rb]
  za,zb,ra,rb,a,b = zb,za,rb,ra,b,a if za<zb
  zab = (za+zb).pow(P-2,P)
  E[ra] += za*zab
  E[rb] += zb*zab
  G[ra] += G[rb]
  G[rb] = ra
  E[rb] -= E[ra]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

P = 998244353
N = gets.to_i
G = [-1]*N
E = [0]*N
F = lambda{|a|
	next a if G[a]<0
	ra = G[a]
	G[a] = F[ra]
	E[a] += E[ra] if ra!=G[a]
	next G[a]
}
U = lambda{|a,b|
	ra,rb = F[a],F[b]
	za,zb = -G[ra],-G[rb]
	za,zb,ra,rb,a,b = zb,za,rb,ra,b,a if za<zb
	zab = (za+zb).pow(P-2,P)
	E[ra] += za*zab
	E[rb] += zb*zab
	G[ra] += G[rb]
	G[rb] = ra
	E[rb] -= E[ra]
}

(N-1).times{
	U[*gets.split.map{_1.to_i-1}]
}
R = F[0]
E0 = E[R]%P
N.times.each(&F)

puts E.map.with_index{|e,a| a==R ? E0 : (E0+e)%P }*' '

Submission Info

Judge Result