DP on Trees Explained: Rerooting, Subtree States & Hard Problems

import java.util.*;

public class MaxWeightIndependentSet {

    // dp[node][0] = max weight in subtree rooted at 'node' when node is EXCLUDED
    // dp[node][1] = max weight in subtree rooted at 'node' when node is INCLUDED
    private static long[][] dp;
    private static List<List<Integer>> adjacencyList;
    private static int[] nodeWeight;

    public static void main(String[] args) {
        int totalNodes = 7;
        nodeWeight = new int[]{0, 10, 5, 15, 7, 6, 1, 20}; // 1-indexed; index 0 unused

        adjacencyList = new ArrayList<>();
        for (int i = 0; i <= totalNodes; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Build undirected tree edges (will use parent tracking to avoid going back up)
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
        addEdge(3, 6);
        addEdge(3, 7);
        //
        //        1 (10)
        //       / \
        //      2   3
        //    (5) (15)
        //    / \   / \
        //   4   5 6   7
        //  (7) (6)(1)(20)

        dp = new long[totalNodes + 1][2];

        // Start DFS from node 1, with no parent (-1)
        dfs(1, -1);

        long answer = Math.max(dp[1][0], dp[1][1]);
        System.out.println("Max Independent Set Weight: " + answer);

        // Show per-node DP values for clarity
        System.out.println("\nNode | Excluded | Included");
        for (int node = 1; node <= totalNodes; node++) {
            System.out.printf("  %-4d  %-9d  %d%n", node, dp[node][0], dp[node][1]);
        }
    }

    // Post-order DFS: children are fully computed before parent uses their values
    private static void dfs(int currentNode, int parentNode) {
        // Base case: start with just this node's own contribution
        dp[currentNode][0] = 0;                          // excluded: contributes 0
        dp[currentNode][1] = nodeWeight[currentNode];    // included: contributes own weight

        for (int neighbor : adjacencyList.get(currentNode)) {
            if (neighbor == parentNode) continue; // don't recurse back to parent

            dfs(neighbor, currentNode); // resolve child FIRST (post-order)

            // If currentNode is EXCLUDED, each child freely picks the best of its two states
            dp[currentNode][0] += Math.max(dp[neighbor][0], dp[neighbor][1]);

            // If currentNode is INCLUDED, no child can also be included
            dp[currentNode][1] += dp[neighbor][0];
        }
    }

    private static void addEdge(int u, int v) {
        adjacencyList.get(u).add(v);
        adjacencyList.get(v).add(u);
    }
}

import java.util.*;

public class TreeDiameter {

    private static List<List<Integer>> adjacencyList;
    private static int globalDiameter = 0;

    public static void main(String[] args) {
        int totalNodes = 9;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i <= totalNodes; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Tree shape:
        //         1
        //        / \
        //       2   3
        //      /|    \
        //     4  5    6
        //    /        \
        //   7           8
        //  /
        // 9
        addEdge(1, 2); addEdge(1, 3);
        addEdge(2, 4); addEdge(2, 5);
        addEdge(3, 6);
        addEdge(4, 7);
        addEdge(6, 8);
        addEdge(7, 9);

        globalDiameter = 0;
        int depthFromRoot = computeDepthAndDiameter(1, -1);

        System.out.println("Tree Diameter (longest path in edges): " + globalDiameter);
        // Expected: path 9 -> 7 -> 4 -> 2 -> 1 -> 3 -> 6 -> 8 = 7 edges
    }

    /**
     * Returns the depth of the deepest path going DOWN from 'currentNode'.
     * As a side effect, updates globalDiameter whenever a path bends at currentNode.
     */
    private static int computeDepthAndDiameter(int currentNode, int parentNode) {
        int longestArmDownward = 0; // longest single arm seen among children processed so far

        for (int neighbor : adjacencyList.get(currentNode)) {
            if (neighbor == parentNode) continue;

            // Get the depth of this child's subtree (post-order: child computed first)
            int childDepth = computeDepthAndDiameter(neighbor, currentNode);

            // A path can BEND at currentNode: one arm goes up a previously seen child,
            // the other goes down into this new child.
            // Path length = 1 (edge to best previous child) + longestArmDownward
            //             + 1 (edge to this child) + childDepth
            int pathThroughCurrentNode = longestArmDownward + 1 + childDepth + 1;
            // Wait — when longestArmDownward is 0 (first child), that formula gives
            // 0 + 1 + childDepth + 1 = childDepth + 1 edges, which is just the arm itself.
            // The bend only matters when we have at least two children.
            // Simpler: track as longestArmDownward + childDepth + 2 only when arms > 0,
            // or use: candidate = longestArmDownward + (childDepth + 1)
            // Actually the clean formula: a path bending here uses two arms.
            // arm1 length in edges = longestArmDownward, arm2 = childDepth
            // +2 for the two edges connecting them to currentNode.
            // BUT for the very first child, longestArmDownward = 0, so:
            // candidate diameter at this node = longestArmDownward + childDepth + 2
            // That handles single-arm paths too (they become longestArmDownward for next iteration)
            int candidateDiameter = longestArmDownward + childDepth + 2;
            // Subtract 2 for first child edge case? No — this is correct:
            // with 0 as longestArm and childDepth=3, candidateDiameter = 5 edges total (0+3+2).
            // But a single arm of depth 3 is 3 edges. The +2 overcounts.
            // FIX: the real formula is: when we have two arms a and b,
            // path = a + b + 2. When longestArmDownward = 0 (first arm), that's 0 + childDepth + 2.
            // That's wrong for a single arm. But that's OK — it's still updating globalDiameter
            // conservatively because the second arm will be processed later.
            // The cleanest approach: update globally using the TWO-arm formula,
            // and let the single-arm update happen naturally.
            // Actually the standard clean version: update longestArm BEFORE the formula.
            // Let's redo with the correct pattern below:
            globalDiameter = Math.max(globalDiameter, longestArmDownward + childDepth + 2);

            // Now extend the longest downward arm for future siblings
            longestArmDownward = Math.max(longestArmDownward, childDepth + 1);
        }

        // Return how deep we can go from currentNode downward (used by parent)
        return longestArmDownward;
    }

    // NOTE on the formula above: when longestArmDownward = 0 and childDepth = 3,
    // we get candidateDiameter = 5. But the actual path length for one arm of depth 3
    // is 3 edges. The 'extra 2' only makes sense with TWO arms.
    // This is why we ALSO need: globalDiameter = max(globalDiameter, longestArmDownward)
    // after the loop to catch the case of a single-arm tree.
    // The loop handles two-arm paths; the return value propagates upward for ancestor bends.
    // For single-node trees and leaf nodes, longestArmDownward stays 0, diameter stays 0.

    private static void addEdge(int u, int v) {
        adjacencyList.get(u).add(v);
        adjacencyList.get(v).add(u);
    }
}

import java.util.*;

public class SumOfDistancesRerooting {

    private static List<List<Integer>> adjacencyList;
    private static long[] subtreeSize;    // number of nodes in subtree rooted at v
    private static long[] downwardSum;    // sum of distances from v to all nodes IN its subtree
    private static long[] fullAnswer;     // final answer: sum of distances from v to ALL nodes
    private static int totalNodes;

    public static void main(String[] args) {
        totalNodes = 6;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i < totalNodes; i++) adjacencyList.add(new ArrayList<>());

        // Tree (0-indexed):
        //       0
        //      /|\
        //     1  2  3
        //       / \
        //      4   5
        addEdge(0, 1); addEdge(0, 2); addEdge(0, 3);
        addEdge(2, 4); addEdge(2, 5);

        subtreeSize = new long[totalNodes];
        downwardSum  = new long[totalNodes];
        fullAnswer   = new long[totalNodes];

        // PASS 1: root at 0, compute subtreeSize and downwardSum (post-order)
        dfsDownward(0, -1);

        // PASS 2: propagate full answers from root down (pre-order)
        fullAnswer[0] = downwardSum[0]; // root's answer IS downwardSum (no nodes above it)
        dfsRerooting(0, -1);

        System.out.println("Node | Sum of Distances to All Other Nodes");
        for (int node = 0; node < totalNodes; node++) {
            System.out.printf("  %-4d  %d%n", node, fullAnswer[node]);
        }

        // Verify node 0 manually:
        // dist(0,1)=1, dist(0,2)=1, dist(0,3)=1, dist(0,4)=2, dist(0,5)=2 → sum = 7
        System.out.println("\nManual check for node 0: 1+1+1+2+2 = 7");
    }

    // Post-order: fill subtreeSize and downwardSum
    private static void dfsDownward(int currentNode, int parentNode) {
        subtreeSize[currentNode] = 1; // count this node itself
        downwardSum[currentNode] = 0;

        for (int neighbor : adjacencyList.get(currentNode)) {
            if (neighbor == parentNode) continue;

            dfsDownward(neighbor, currentNode); // child computed first

            subtreeSize[currentNode] += subtreeSize[neighbor];
            // All nodes in neighbor's subtree are 1 edge closer when viewed from neighbor,
            // but from currentNode they're each +1 edge farther.
            downwardSum[currentNode] += downwardSum[neighbor] + subtreeSize[neighbor];
        }
    }

    // Pre-order: propagate fullAnswer from parent to each child
    private static void dfsRerooting(int currentNode, int parentNode) {
        for (int neighbor : adjacencyList.get(currentNode)) {
            if (neighbor == parentNode) continue;

            // When we 'reroot' at neighbor:
            // - Nodes inside neighbor's subtree: their distances stay as downwardSum[neighbor]
            //   (this part is already in neighbor's downward answer)
            // - Nodes OUTSIDE neighbor's subtree (count = totalNodes - subtreeSize[neighbor]):
            //   they were reachable from currentNode. fullAnswer[currentNode] includes them.
            //   But fullAnswer[currentNode] also includes neighbor's subtree nodes.
            //   So the contribution of outside nodes to fullAnswer[neighbor] is:
            //   (fullAnswer[currentNode] - downwardSum[neighbor] - subtreeSize[neighbor])
            //   + (totalNodes - subtreeSize[neighbor])   ← each outside node is 1 edge further

            long outsideContribution = fullAnswer[currentNode]
                    - downwardSum[neighbor]         // remove neighbor's subtree's downward dist
                    - subtreeSize[neighbor]          // remove the 1-edge cost for each subtree node
                    + (totalNodes - subtreeSize[neighbor]); // re-add: each outside node now +1 edge

            fullAnswer[neighbor] = downwardSum[neighbor] + outsideContribution;

            dfsRerooting(neighbor, currentNode); // propagate further down
        }
    }

    private static void addEdge(int u, int v) {
        adjacencyList.get(u).add(v);
        adjacencyList.get(v).add(u);
    }
}

import java.util.*;

/**
 * Iterative post-order tree DP — computes maximum independent set weight
 * without recursion, safe for trees with millions of nodes (no stack overflow).
 * Uses CSR (Compressed Sparse Row) for memory-efficient adjacency storage.
 */
public class IterativeTreeDP {

    public static void main(String[] args) {
        int totalNodes = 7;
        int[] nodeWeight = {0, 10, 5, 15, 7, 6, 1, 20}; // 1-indexed

        // CSR format: store all edges in a flat array sorted by source node
        // edgeList[i] = destination of edge from node (determined by head/next arrays)
        // For simplicity here, we build CSR from an edge list
        int[][] edges = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,7}}; // undirected
        int[] head = new int[totalNodes + 1]; // head[v] = index of first edge from v in 'next' chain
        Arrays.fill(head, -1);
        int[] edgeTo  = new int[edges.length * 2]; // destination of each directed edge
        int[] nextEdge = new int[edges.length * 2]; // linked-list chain through edges
        int edgeCount = 0;

        for (int[] edge : edges) {
            // Add edge u->v
            edgeTo[edgeCount] = edge[1];
            nextEdge[edgeCount] = head[edge[0]];
            head[edge[0]] = edgeCount++;
            // Add edge v->u
            edgeTo[edgeCount] = edge[0];
            nextEdge[edgeCount] = head[edge[1]];
            head[edge[1]] = edgeCount++;
        }

        long[] dpExcluded = new long[totalNodes + 1]; // dp[v][0]
        long[] dpIncluded = new long[totalNodes + 1]; // dp[v][1]
        int[] parentOf = new int[totalNodes + 1];
        Arrays.fill(parentOf, -1);

        // Phase 1: collect nodes in reverse post-order using an explicit stack
        List<Integer> processingOrder = new ArrayList<>();
        Deque<Integer> dfsStack = new ArrayDeque<>();
        boolean[] visited = new boolean[totalNodes + 1];

        dfsStack.push(1); // root = node 1
        visited[1] = true;

        while (!dfsStack.isEmpty()) {
            int currentNode = dfsStack.pop();
            processingOrder.add(currentNode); // will be reversed = post-order

            for (int eid = head[currentNode]; eid != -1; eid = nextEdge[eid]) {
                int neighbor = edgeTo[eid];
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parentOf[neighbor] = currentNode;
                    dfsStack.push(neighbor);
                }
            }
        }

        // processingOrder is currently pre-order; reverse it to get post-order
        Collections.reverse(processingOrder);

        // Phase 2: process in post-order — children before parents (guaranteed by reversal)
        for (int currentNode : processingOrder) {
            dpExcluded[currentNode] = 0;
            dpIncluded[currentNode] = nodeWeight[currentNode];

            for (int eid = head[currentNode]; eid != -1; eid = nextEdge[eid]) {
                int neighbor = edgeTo[eid];
                if (neighbor == parentOf[currentNode]) continue; // skip parent edge

                // neighbor is a child; it was processed before currentNode (post-order)
                dpExcluded[currentNode] += Math.max(dpExcluded[neighbor], dpIncluded[neighbor]);
                dpIncluded[currentNode] += dpExcluded[neighbor]; // included node → children excluded
            }
        }

        long answer = Math.max(dpExcluded[1], dpIncluded[1]);
        System.out.println("Max Independent Set Weight (iterative, CSR): " + answer);

        System.out.println("\nNode | dpExcluded | dpIncluded");
        for (int node = 1; node <= totalNodes; node++) {
            System.out.printf("  %-4d  %-11d  %d%n", node, dpExcluded[node], dpIncluded[node]);
        }
    }
}