Maximum Weighted Connected Subset

Given a set \(V\) of integer points in the plane, where each point \(P=(x,y)\) has an integer weight \(w\). The set \(V\) satisfies the following properties:

• Every point in \(V\) is an integer point, i.e. both \(x\) and \(y\) are integers.
• For any two distinct points \(P_1=(x_1,y_1)\) and \(P_2=(x_2,y_2)\) in \(V\), if \(|x_1-x_2|+|y_1-y_2| = 1\), then they are considered adjacent (neighbors). Otherwise, they are not adjacent.
• \(V\) is a single integral point set: for any two points in \(V\), there exists exactly one path (a sequence of distinct points \(Q_1, Q_2,\dots, Q_k\) where each consecutive pair is adjacent) connecting them. In other words, the graph defined by \(V\) and the neighbor relation is a tree.

Each point \(P_i\) in \(V\) is assigned an integer weight \(w_i\). The weight sum of any subset \(B \subseteq V\) is defined as the sum of weights of the points in \(B\).

Your task is to find an optimal connected subset \(B\) of \(V\) that satisfies:

1. \(B\) is a subset of \(V\) (\(B \subseteq V\)).
2. For any two points in \(B\), there exists a path within \(B\) connecting them (i.e. \(B\) is connected).
3. Among all connected subsets of \(V\), \(B\) has the maximum possible weight sum.

Note: \(B\) must be non-empty. If all weights are negative, the answer is the maximum single weight.

Hint: Since \(V\) forms a tree, you can use a tree dynamic programming (DP) approach. One common idea is to perform a DFS and compute for every node \(u\) a value

[ dp[u] = w_u + \sum_{v \text{ is a child of } u} \max(0, dp[v]). ]

The answer will be (\max_{u \in V} dp[u]).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)), the number of points in \(V\). Each of the following \(n\) lines contains three integers \(x, y, w\), representing the coordinates and weight of a point. It is guaranteed that the given points form a tree with respect to the neighbor relation, i.e. for any two points \((x_1, y_1)\) and \((x_2, y_2)\) in \(V\), if \(|x_1-x_2|+|y_1-y_2|=1\) then they are directly connected by an edge, and \(V\) is connected with exactly \(n-1\) edges.

You may assume that the points are distinct.

outputFormat

Output a single integer representing the maximum weight sum of a connected subset of \(V\).

sample

3
0 0 1
0 1 -2
0 2 3

3