fork download
copy 
  1. # your code goes here
  2. from collections import defaultdict
  3.  
  4.  
  5. def max_p(start):
  6.     # print(root[1])
  7.     return max(-x, d[start][0] + sum(map(max_p, d[start][1])))
  8.  
  9.  
  10. for _ in range(int(input())):
  11.     n, x = map(int, input().split())
  12.     arr = list(map(int, input().split()))
  13.     d = defaultdict(list)
  14.     best_node = []
  15.     for i in range(n):
  16.         d[i + 1] = [arr[i], [], 0]
  17.  
  18.     for i in range(n - 1):
  19.         a, b = map(int, input().split())
  20.         d[a][1].append(b)
  21.  
  22.     p = max_p(1)
  23.     # print(d)
  24.     print(p)
  25.  
  26. '''
  27. Test 1
  28. 2
  29. 12 5
  30. 5 2 10 5 6 3 -10 20 4 10 -15 -20
  31. 1 2
  32. 1 3
  33. 3 4
  34. 3 5
  35. 2 6
  36. 6 7
  37. 6 8
  38. 6 9
  39. 9 10
  40. 9 11
  41. 9 12
  42. 5 -4
  43. 5 6 -6 9 8
  44. 1 2
  45. 2 3
  46. 3 4
  47. 3 5
  48. '''
Success #stdin #stdout 0.02s 27704KB
comments (?)
stdin
copy 
1
3 5
1 -5 -10
1 2
2 3
stdout
copy 
-4
https://ideone.com/JsVXlp
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!