Submission #50187841

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
A = gets.split.map(&:to_i)
E = Array.new(N){{}}
(N-1).times{
  u,v = gets.split.map{_1.to_i-1}
  E[u][v] = v
  E[v][u] = u
}
X = [nil]*N
C = Array.new(N){[]}
Q = N.times.select{|a| E[a].size==1 }
while u = Q.shift
  v, = E[u].shift
  a2ts = Hash.new{|h,a| h[a] = [] }
  C[u].each{|a2t|
    a2t.each{|a,t|
      a2ts[a]<<t
    }
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

X = [nil]*N
C = Array.new(N){[]}
Q = N.times.select{|a| E[a].size==1 }
while u = Q.shift
	v, = E[u].shift
	a2ts = Hash.new{|h,a| h[a] = [] }
	C[u].each{|a2t|
		a2t.each{|a,t|
			a2ts[a]<<t
		}
	}
	a2t = a2ts.transform_values{|ts|
		ts.inject(0){|s,t| ((s+1)*(t+1)-1)%P }
	}
	a2t[A[u]] ||= 0
	a2t[A[u]] += 1
	X[u] = a2t.values.sum-a2ts.values.sum(&:sum)+a2ts[A[u]].sum
	break unless v
	C[v]<<a2t
	E[v].delete u
	Q<<v if E[v].size==1
end

p X.sum%P

Submission Info

Judge Result