[BOJ] 백준 [17831] 대기업 승범이네 JAVA

[BOJ] 백준 [17831] 대기업 승범이네 JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream.Collectors;

public class Main {

static ArrayList < Integer > [] list;

static int [][] dp;

static int [] weight;

static int n;

public static void main( String [] args) throws IOException {

BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));

n = Integer. parseInt (br.readLine());

list = new ArrayList[n + 1 ];

weight = new int [n + 1 ];

dp = new int [n + 1 ][ 2 ];

for ( int i = 1 ;i < = n;i + + ) list[i] = new ArrayList < > ();

int [] input = Arrays.stream(br.readLine(). split ( " " ))

.mapToInt(Integer:: parseInt ).toArray();

for ( int i = 0 ;i < input. length ;i + + ) list[input[i]]. add (i + 2 );

input = Arrays.stream(br.readLine(). split ( " " ))

.mapToInt(Integer:: parseInt ).toArray();

for ( int i = 1 ;i < = n;i + + ) {

Arrays.fill(dp[i], - 1 );

weight[i] = input[i - 1 ];

}

System . out . println (dfs( 1 , 0 ));

}

private static int dfs( int cur, int isBind) {

if (dp[cur][isBind] ! = - 1 ) return dp[cur][isBind];

dp[cur][isBind] = 0 ;

for (Integer next : list[cur]) dp[cur][isBind] + = dfs(next, 0 );

if (isBind = = 0 ){

int sum = dp[cur][isBind];

for (Integer next : list[cur])

dp[cur][isBind] = Math.max(dp[cur][isBind],

sum - dfs(next, 0 ) + dfs(next, 1 ) + weight[cur] * weight[next]);

}

return dp[cur][isBind];

}

}

from http://katastrophe.tistory.com/79 by ccl(A) rewrite - 2021-11-08 19:00:48