Java detailed 
Placing Coins on a TreeApproachTo solve the problem, we leverage DFS (Depth-First Search) and sorting to process the tree structure. Here's the step-by-step bre
### **Placing Coins on a Tree**



#### **Approach**

To solve the problem, we leverage **DFS (Depth-First Search)** and **sorting** to process the tree structure. Here's the step-by-step breakdown:

---

#### **1. Graph Representation**
We represent the tree using an adjacency list:
- Use a `Map<Integer, List<Integer>>` to store edges.
- For each edge `[u, v]`, add `v` to the adjacency list of `u` and vice versa.

#### **2. DFS Traversal**
We perform a DFS starting from the root node (`0`), passing the following:
- `parent` to avoid revisiting the parent node.
- `curr` to represent the current node.

At each node:
- Collect all coin values from the current node and its child nodes.
- Sort the values.
- Select up to 5 values to compute the result for the current node.

#### **3. Computation**
For each node:
- If it has fewer than 3 coins, set `ans[i] = 1`.
- Otherwise, calculate the maximum product of three values:
  - Use the smallest two (`temp[0]` and `temp[1]`) to handle negative values.
  - Use the largest three (`temp[n-3]`, `temp[n-2]`, `temp[n-1]`) to maximize the result.

---

#### **Algorithm**

```java
class Solution {
    public long[] placedCoins(int[][] edges, int[] cost) {
        // Step 1: Build the graph
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            map.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            map.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }

        int n = cost.length;
        long[] ans = new long[n];
        Arrays.fill(ans, 0L);

        // Step 2: Perform DFS starting from node 0
        dfs(map, cost, ans, 0, -1);
        return ans;
    }

    private List<Integer> dfs(Map<Integer, List<Integer>> map, int[] cost, long[] ans, int curr, int parent) {
        // List to store coin values from the current node and its children
        List<Integer> temp = new ArrayList<>();

        for (int adj : map.getOrDefault(curr, new ArrayList<>())) {
            if (adj != parent) {
                temp.addAll(dfs(map, cost, ans, adj, curr));
            }
        }

        // Add the current node's cost
        temp.add(cost[curr]);

        // Sort the list of coin values
        Collections.sort(temp);

        int n = temp.size();
        if (n >= 3) {
            long left = (long) temp.get(0) * temp.get(1); // Product of the smallest two
            long right = (long) temp.get(n - 3) * temp.get(n - 2); // Product of the largest two
            ans[curr] = Math.max(0, Math.max(left, right) * temp.get(n - 1));
        } else {
            ans[curr] = 1; // Not enough coins to compute a product
        }

        // Return up to 5 coins for use in the parent node's calculation
        if (n <= 5) return temp;

        return new ArrayList<>(Arrays.asList(
            temp.get(0), temp.get(1), temp.get(n - 3), temp.get(n - 2), temp.get(n - 1)
        ));
    }
}
```

---

#### **Example**

##### Input:
```plaintext
edges = [[0,1],[0,2],[1,3],[1,4],[1,5],[2,6],[2,7],[2,8]]
cost = [1,4,2,3,5,7,8,-4,2]
```

##### Output:
```plaintext
[280, 140, 32, 1, 1, 1, 1, 1, 1]
```

##### Explanation:
1. **Graph Representation:**
   ```
   0 -> [1, 2]
   1 -> [0, 3, 4, 5]
   2 -> [0, 6, 7, 8]
   ```
2. **DFS Execution:**
   - At node `1`, collect `[3, 5, 7, 4]`.  
     - Compute `140` as the maximum product.
   - At node `2`, collect `[8, -4, 2, 2]`.  
     - Compute `32` as the maximum product.
   - At node `0`, collect `[140, 32, 1]` and compute `280`.

---

#### **Complexity Analysis**
1. **Time Complexity:**
   - **Graph Construction:** `O(n)`
   - **DFS Traversal:** `O(n * log(k))`, where `k` is the maximum number of coins at any node (at most 5).
   - Overall: `O(n * log(5)) ≈ O(n)`

2. **Space Complexity:**
   - Graph storage: `O(n)`
   - DFS recursion stack: `O(n)`
   - Total: `O(n)`

---

#### **Why This Approach Works**
- Using DFS ensures that we only visit each node once.
- The parent-child relationship naturally avoids revisits without requiring an explicit `visited` array.
- Sorting and limiting to 5 coins reduces unnecessary computations.

---

#### **Edge Cases**
1. **Small Trees:**
   - Input: `edges = [[0,1]], cost = [1, 2]`
   - Output: `[1, 1]`

2. **Negative Costs:**
   - Input: `edges = [[0,1],[1,2]], cost = [-1, -2, -3]`
   - Output: `[0, 1, 1]`

3. **All Positive Costs:**
   - Input: `edges = [[0,1],[1,2]], cost = [1, 2, 3]`
   - Output: `[6, 1, 1]`

---


['Java']