Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met:

Upon removing any arbitrary node, the total weight of nodes in each resulting connected component should be equal.

Consider the following tree as an example:

1 -- 2 -- -3 -- 4
     |
     1

In this tree, if we remove any node, the total weight of the nodes in each of the resulting connected components is equal. For instance, if we remove the node with weight $-3$, we end up with two connected components, each with a total weight of $4$.

I am seeking an algorithm that can find these weights in polynomial time.

My initial approach was to assign arbitrary values to the nodes. Then, for each node, I would check if the condition is satisfied when that node is removed. This check can be performed in $O(n)$ time using graph traversal algorithms like BFS or DFS. However, I am unsure how to adjust the tree because correcting the condition for one node seems to disrupt the condition for almost all other nodes.

Any suggestions or insights would be greatly appreciated.

Using the idea of @Mahyar, I think there is another way to find a solution to the problem.

Given a tree $T= (V, E)$, find a bipartition of $T = (X\sqcup Y, E)$ (using a simple graph traversal). Consider the following weighting function:

$$w : \begin{array}[t]{rcl}
V & \to & \mathbb{Z}\\
v & \mapsto & \left\{\begin{array}{ll} \deg(v) & \text{if }v\in X\\-\deg(v)&\text{if }v\in Y\end{array}\right.
\end{array}$$

Then it satisfies the property.

Indeed, when deleting a vertex of $X$, the resulting connected components are of weight $-1$. When deleting a vertex of $Y$, the resulting connected components are of weight $1$. The total weight of the tree is $0$.

Proof:

• $w(T) = 0$. Indeed, $w(T) = \sum\limits_{x\in X}\deg(x) - \sum\limits_{y\in Y}\deg(y) = 0$, because the graph is bipartite.

• Deleting a node of $X$ (resp. $Y$) creates connected components of weight $-1$ (resp. $1$). The idea of the proof is basically the same as in @Mahyar's answer: we consider $r\in V$ an arbitrary root. For $v\in V$, we note $h(v)$ the maximal distance from $v$ to a leaf of the tree $T$ rooted in $r$. We prove by induction on $h(v)$ that the result is true.

-
if $h(v) = 0$, $v$ is a leaf, hence of weight $1$ or $-1$. Deleting $v$ creates one connected component of weight $-w(v)$, because $w(T) = 0$;

-
suppose the result true for all $v$ such that $h(v) \leqslant k$, for some $k\geqslant 0$. Let $x\in X\setminus \{r\}$ (the case $Y$ is similar) such that $h(x) = k + 1$. In the tree $T$ rooted in $r$, all children of $x$, $v_1, v_2, …, v_{d-1}$, with $d = \deg(x)$, verify $h(v_i) \leqslant k$. Let $T_i$ be the subtree rooted in $v_i$.

Since each $v_i\in Y$, using induction hypothesis, for all $i$, $w(T\setminus T_i) = 1$. That means that $w(T_i) = w(T) - w(T\setminus T_i) = -1$. Now, the connected components created by the deletion of $x$ are the $T_i$'s, and the rest of the tree: $T\setminus (\{x\}\cup T_1 \cup… \cup T_{d-1})$. The weight of this connected component is:
$$w(T) - w(x) - w(T_1) - … - w(T_{d-1}) = -1$$

-
the case of the root is similar, just without this last connected component.

StackExchange Computer Science Q#167177, answer score: 9