Implementing a recursive algorithm for tree.

[Negativ3]

I'm trying to solve

You are given a rooted tree with N nodes (numbered 1 through N); node 1 is the root. Each node has a value; let's denote the value of node i by Ai.

You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.

Let's define the profit as the sum of values of all nodes which currently exist in the tree minus X⋅k, where k denotes the number of times this operation was performed. Find the maximum possible profit.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and X.
The second line contains N space-separated integers A1,A2,…,AN.
Each of the following N−1 lines contains two space-separated integers u and v denoting that nodes u and v are connected by an edge.
Output
For each test case, print a single line containing one integer — the maximum profit.

Constraints
1≤T≤10
1≤N≤105
1≤X≤109
1≤u,v≤N
|Ai|≤109 for each valid i
the graph described on the input is a tree
Subtasks
Subtask #1 (30 points): 1≤N≤1,000
Subtask #2 (70 points): original constraints

Example Input
1
3 5
1 -5 -10
1 2
2 3
Example Output
-4

here is what I came up with.

class Node:
    def __init__(self, identifier):
        self.__identifier = identifier
        self.__children = []

    @property
    def identifier(self):
        return self.__identifier

    @property
    def children(self):
        return self.__children

    def add_child(self, identifier):
        self.__children.append(identifier)

(_ROOT, _DEPTH, _BREADTH) = range(3)


class Tree:

    def __init__(self,x):
        self.__nodes = {}
        self.x = x

    @property
    def nodes(self):
        return self.__nodes

    def add_node(self, identifier, parent=None):
        node = Node(identifier)
        self[identifier] = node

        if parent is not None:
            self[parent].add_child(identifier)

        return node

    def display(self, identifier, depth=_ROOT):
        children = self[identifier].children
        if depth == _ROOT:
            print("{0}".format(identifier))
        else:
            print("\t"*depth, "{0}".format(identifier))

        depth += 1
        for child in children:
            self.display(child, depth)  # recursive call

    def traverse(self, identifier, mode=_DEPTH):
        # Python generator. Loosly based on an algorithm from 
        # 'Essential LISP' by John R. Anderson, Albert T. Corbett, 
        # and Brian J. Reiser, page 239-241
        yield identifier
        queue = self[identifier].children
        while queue:
            yield queue[0]
            expansion = self[queue[0]].children
            if mode == _DEPTH:
                queue = expansion + queue[1:]  # depth-first
            elif mode == _BREADTH:
                queue = queue[1:] + expansion  # width-first
    def max_profit(self,identifier):

        return max(-x,self[identifier] + sum(map(max_profit, self[identifier].children)))
    def __getitem__(self, key):
        return self.__nodes[key]

    def __setitem__(self, key, item):
        self.__nodes[key] = item



for i in range(int(input())):
    n,x = map(int,input().split())
    weight = list(map(int,input().strip().split()))
    summ = sum(weight)
    sumWeight = summ
    dic = dict()
    tree = Tree(x)
    tree.add_node(weight[0])
    for i in range(n-1):
        a,b = map(int,input().split())

        if a not in dic.keys():
            dic[weight[a-1]] = weight[b-1]
        else:
            dic[weight[a-1]].append(weight[b])
        if b not in dic.keys():
            dic[weight[b-1]] = weight[a-1]
        else:
            dic[weight[b-1]].append(weight[a-1])
        tree.add_node(weight[b-1],weight[a-1])
    print(dic)
    for i in tree.traverse(1,_BREADTH):
        print(i)
    y = tree.max_profit(1)
    print(y)

I'm not familiar with OOP's so,
What I need is to make the max_profit function work.
Any help will be appreciate.