트리 DP

전처리

static class Edge
{
    int next_node;
    Edge next_edge;

    Edge (int next_node, Edge next_edge) 
    { 
        this.next_node = next_node; 
        this.next_edge = next_edge; 
    }
}

int[] weight = new int[N+1];
int[][] dp = new int[N+1][2];
Edge[] graph = new Edge[N+1];


for (int i=1; i<=N-1; i++)
{
    st = new StringTokenizer(input.readLine());

    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());

    graph[u] = new Edge(v, graph[u]);
    graph[v] = new Edge(u, graph[v]);
}

 

 

트리 DP

static void Tree_Dp (int[][] dp, int[] weight, Edge[] graph, int current_node, int parent)
{
    dp[current_node][0] = 0;
    dp[current_node][1] = weight[current_node];

    for (Edge edge = graph[current_node]; edge != null; edge = edge.next_edge)
    {
        if ( edge.next_node != parent )
        {
            int next_node = edge.next_node;
            Tree_Dp(dp, weight, graph, next_node, current_node);
            dp[current_node][0] += Math.max(dp[next_node][0], dp[next_node][1]);
            dp[current_node][1] += dp[next_node][0];
        }
    }
}