Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def tree(lst, n):
- res = [[] for i in range(n+1)]
- for i in lst:
- res[i[0]].append(i[1])
- res[i[1]].append(i[0])
- return res
- def dfs(cur, par, adj_tree, diameter, height):
- max1 = 0
- max2 = 0
- for u in adj_tree[cur]:
- if u == par:
- continue
- dfs(u, cur, adj_tree, diameter, height)
- height[cur] = max(height[cur], height[u])
- if height[u] >= max1:
- max2 = max1
- max1 = height[u]
- elif height[u] > max2:
- max2 = height[u]
- height[cur] += 1
- return max(diameter, height[cur], max1 + max2 + 1)
- def find_min_height_trees(n, tree):
- if n <= 2: return n - 1
- count = 0
- leaves = []
- for i in range(1, n+1):
- if len(tree[i]) == 1:
- leaves.append(i)
- remaining_nodes = n
- while remaining_nodes > 2:
- remaining_nodes -= len(leaves)
- new_leaves = []
- while leaves:
- leaf = leaves.pop()
- neighbor = tree[leaf].pop()
- tree[neighbor].remove(leaf)
- if len(tree[neighbor]) == 1:
- new_leaves.append(neighbor)
- count += 1
- leaves = new_leaves
- return count + (remaining_nodes // 2)
- n = int(input())
- lst1 = [tuple(map(int, input().split())) for i in range(n - 1)]
- adj_tree1 = tree(lst1, n)
- m = int(input())
- lst2 = [tuple(map(int, input().split())) for j in range(m - 1)]
- adj_tree2 = tree(lst2, m)
- print('L' if find_min_height_trees(n, adj_tree1) > (dfs(1, 0, adj_tree2, 0, [0 for i in range(m + 1)]) - 1) else 'D')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement