output_description: Print the lexicographically smallest permutation, with spaces in between.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      p_1 p_2 ... p_N
attempt: import sys
  
  sys.setrecursionlimit(10**6)
  
  
  def input():
      return sys.stdin.readline()[:-1]
  
  
  n = int(input())
  a = list(map(int, input().split()))
  adj = [[] for _ in range(n)]
  for _ in range(n - 1):
      s, t = map(int, input().split())
      adj[s - 1].append(t - 1)
      adj[t - 1].append(s - 1)
  par = [-1 for _ in range(n)]
  aff = [0 for _ in range(n)]
  
  
  def dfs(x, p):
      for v in adj[x]:
          if v == p:
              continue
          aff[x] += 1
          par[v] = x
          dfs(v, x)
      return
  
  
  dfs(0, -1)
  af_lis = [[] for _ in range(n)]
  zero = [i for i in range(n) if aff[i] == 0]
  
  
  def check(x):
      if af_lis[x] == []:
          af_lis[par[x]].append(a[x])
          aff[par[x]] -= 1
          if aff[par[x]] == 0:
              zero.append(par[x])
          return
      s, ma = sum(af_lis[x]), max(af_lis[x])
      if ma * 2 > s:
          s_mi = ma
      else:
          s_mi = (s + 1) // 2
      if s_mi <= a[x] <= s:
          if par[x] == -1:
              if 2 * a[x] != s:
                  print("NO")
                  sys.exit()
              else:
                  return
          af_lis[par[x]].append(2 * a[x] - s)
          aff[par[x]] -= 1
          if aff[par[x]] == 0:
              zero.append(par[x])
          return
      else:
          print("NO")
          sys.exit()
          return
  
  
  while zero:
      check(zero.pop())
  
  print("YES")
  
problem_description: Statement
  
  Let N be a positive even number.
  
  We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Snuke is
  constructing another permutation of (1, 2, ..., N), q, following the procedure
  below.
  
  First, let q be an empty sequence. Then, perform the following operation until
  p becomes empty:
  
    * Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.
  
  When p becomes empty, q will be a permutation of (1, 2, ..., N).
  
  Find the lexicographically smallest permutation that can be obtained as q.
samples: [{"input": "4\n    3 2 4 1", "output": "3 1 2 4\n    \n\nThe solution above is obtained as follows:\n\np | q  \n---|---  \n(3, 2, 4, 1) | ()  \n\u2193 | \u2193  \n(3, 1) | (2, 4)  \n\u2193 | \u2193  \n() | (3, 1, 2, 4)  \n  \n* * *"}, {"input": "2\n    1 2", "output": "1 2\n    \n\n* * *"}, {"input": "8\n    4 6 3 2 8 5 7 1", "output": "3 1 2 7 4 6 8 5\n    \n\nThe solution above is obtained as follows:\n\np | q  \n---|---  \n(4, 6, 3, 2, 8, 5, 7, 1) | ()  \n\u2193 | \u2193  \n(4, 6, 3, 2, 7, 1) | (8, 5)  \n\u2193 | \u2193  \n(3, 2, 7, 1) | (4, 6, 8, 5)  \n\u2193 | \u2193  \n(3, 1) | (2, 7, 4, 6, 8, 5)  \n\u2193 | \u2193  \n() | (3, 1, 2, 7, 4, 6, 8, 5)"}]