Advertisement
daegron

6

Nov 2nd, 2021
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.60 KB | None | 0 0
  1. def tree(lst, n):
  2.     res = [[] for i in range(n+1)]
  3.     for i in lst:
  4.         res[i[0]].append(i[1])
  5.         res[i[1]].append(i[0])
  6.     return res
  7.  
  8.  
  9. def dfs(cur, par, adj_tree, diameter, height):
  10.  
  11.     max1 = 0
  12.     max2 = 0
  13.  
  14.     for u in adj_tree[cur]:
  15.  
  16.         if u == par:
  17.             continue
  18.  
  19.         dfs(u, cur, adj_tree, diameter, height)
  20.  
  21.         height[cur] = max(height[cur], height[u])
  22.  
  23.         if height[u] >= max1:
  24.             max2 = max1
  25.             max1 = height[u]
  26.         elif height[u] > max2:
  27.             max2 = height[u]
  28.  
  29.     height[cur] += 1
  30.  
  31.     return max(diameter, height[cur], max1 + max2 + 1)
  32.  
  33.  
  34. def find_min_height_trees(n, tree):
  35.  
  36.     if n <= 2: return n - 1
  37.  
  38.     count = 0
  39.     leaves = []
  40.  
  41.     for i in range(1, n+1):
  42.         if len(tree[i]) == 1:
  43.             leaves.append(i)
  44.  
  45.     remaining_nodes = n
  46.  
  47.     while remaining_nodes > 2:
  48.  
  49.         remaining_nodes -= len(leaves)
  50.         new_leaves = []
  51.  
  52.         while leaves:
  53.  
  54.             leaf = leaves.pop()
  55.             neighbor = tree[leaf].pop()
  56.             tree[neighbor].remove(leaf)
  57.  
  58.             if len(tree[neighbor]) == 1:
  59.                 new_leaves.append(neighbor)
  60.  
  61.         count += 1
  62.         leaves = new_leaves
  63.  
  64.     return count + (remaining_nodes // 2)
  65.  
  66.  
  67. n = int(input())
  68. lst1 = [tuple(map(int, input().split())) for i in range(n - 1)]
  69. adj_tree1 = tree(lst1, n)
  70. m = int(input())
  71. lst2 = [tuple(map(int, input().split())) for j in range(m - 1)]
  72. adj_tree2 = tree(lst2, m)
  73. 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