Submission #26470241

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N,M,K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
U2V = Array.new(N+1){[]}
E = (N-1).times.map{|e|
  gets.split.map(&:to_i).tap{|u,v|
    U2V[u]<<[v,e]
    U2V[v]<<[u,e]
  }
}
Fs = [nil]*(N-1)
F = lambda{|e,c|
  Fs[e] = A.each_cons(2).count{|u,v| c[u]!=c[v] }
}
C = Array.new(N+1){1<<_1}
D = U2V.map(&:size)
Q = (1..N).select{|u| D[u]<2 }
while u = Q.pop
  c = C[u]
  U2V[u].each{|v,e|
    next if Fs[e]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N,M,K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
U2V = Array.new(N+1){[]}
E = (N-1).times.map{|e|
	gets.split.map(&:to_i).tap{|u,v|
		U2V[u]<<[v,e]
		U2V[v]<<[u,e]
	}
}

Fs = [nil]*(N-1)
F = lambda{|e,c|
	Fs[e] = A.each_cons(2).count{|u,v| c[u]!=c[v] }
}
C = Array.new(N+1){1<<_1}
D = U2V.map(&:size)
Q = (1..N).select{|u| D[u]<2 }
while u = Q.pop
	c = C[u]
	U2V[u].each{|v,e|
		next if Fs[e]
		F[e,c]
		C[v] |= c
		Q << v if 1==D[v]-=1
	}
end

# R+B = Fi.sum
# R-B = K
# 
# R+R = Fi.sum+K

P = 998244353
Fz,Fi = Fs.partition{_1<1}
Z = Fi.size
RR = Fi.sum+K
R = RR/2
S = [{0=>1}]*(Z+1)
#warn [Fz,Fi].inspect

p(R+R!=RR ? 0 : (1..Z).sum{|k|
	S.shift
	ss = Hash.new 0
	(Z-k).downto(0){|i|
		dr = Fi[i]
		S[i].each{|r,s|
			next if R<r+dr
			ss[r+dr] += s
			ss[r+dr] %= P
		}
		S[i] = ss.dup
	}
#warn [k,ss[R],S].inspect
	next ss[R]
}*2.pow(Fz.size,P)%P)

Submission Info

Judge Result