/
035.cr
94 lines (79 loc) · 2.15 KB
/
035.cr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class UnweightedGraph
getter graph : Array(Array(Int32))
def initialize(size : Int)
@graph = Array.new(size) { Array(Int32).new }
end
def add_edge(v, u)
@graph[v] << u
@graph[u] << v
end
delegate size, to: @graph
delegate :[], to: @graph
def pre_order(root : Int32)
result = Array(Int32).new(size)
stack = Deque{ {root, -1} }
while vp = stack.pop?
vertex, parent = vp
result << vertex
self[vertex].reverse_each do |to|
stack << {to, vertex} if to != parent
end
end
result
end
end
class LCA
getter graph : UnweightedGraph
getter depth : Array(Int32)
private def dfs(vertex : Int32, par : Int32, dep : Int32) : Nil
@parent[0][vertex] = par
@depth[vertex] = dep
@graph[vertex].each do |edge|
dfs(edge, vertex, dep + 1) if edge != par
end
end
def initialize(@graph, root : Int32)
@log2 = Math.log2(size).to_i.succ.as(Int32)
@depth = Array(Int32).new(size, -1)
@parent = Array(Array(Int32)).new(@log2) { Array.new(size, 0) }
dfs(root, -1, 0)
(0...@log2 - 1).each do |k|
(0...size).each do |v|
if @parent[k][v] < 0
@parent[k + 1][v] = -1
else
@parent[k + 1][v] = @parent[k][@parent[k][v]]
end
end
end
end
delegate size, to: @graph
def lca(u : Int32, v : Int32) : Int32
u, v = v, u if @depth[u] > @depth[v]
(0...@log2).each do |k|
v = @parent[k][v] if (@depth[v] - @depth[u]).bit(k) == 1
end
return u if u == v
(0...@log2).reverse_each do |k|
u, v = @parent[k][u], @parent[k][v] if @parent[k][u] != @parent[k][v]
end
@parent[0][u]
end
def dist(u : Int32, v : Int32) : Int32
@depth[u] + @depth[v] - @depth[lca(u, v)] * 2
end
end
n = read_line.to_i
graph = UnweightedGraph.new(n)
n.pred.times do
a, b = read_line.split.map(&.to_i.pred)
graph.add_edge(a, b)
end
lca = LCA.new(graph, 0)
order = graph.pre_order(0)
index = [0] * n
(0...n).each { |i| index[order[i]] = i }
read_line.to_i.times do
v = read_line.split.map(&.to_i.pred).skip(1).sort_by! { |i| index[i] }
puts (0...v.size).sum { |i| lca.dist v[i], v[i.succ % v.size] } // 2
end