## Cut the tree _ HackerRank

2018年03月18日 ⁄ 综合 ⁄ 共 1354字 ⁄ 字号 评论关闭

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

static int n;
static int[] nodevals;
static int[] nodesum;
static int root;
static int minDif = Integer.MAX_VALUE;

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

Scanner scan = new Scanner(System.in);
n = scan.nextInt();

nodevals = new int[n+1];
nodesum = new int[n+1];

for(int i = 1;i<=n;i++)
{
nodevals[i] = scan.nextInt();
}

for(int i = 1; i<n;i++)
{
int par = scan.nextInt();
int chd = scan.nextInt();

}

depthSum(1,-1);

depthMinDif(1,-1);

System.out.println(minDif);
}

static int depthSum(int nodeInd,int par)
{
nodesum[nodeInd] += nodevals[nodeInd];

for(int chd : nodes[nodeInd]){

if(chd == par)
continue;

nodesum[nodeInd]+=depthSum(chd,nodeInd);
}
return nodesum[nodeInd] ;
}

static void depthMinDif(int nodeInd, int par){
int tmpdif = Math.abs(nodesum[1] - 2 * nodesum[nodeInd]);
if(tmpdif < minDif)
minDif = tmpdif;

for(int chd : nodes[nodeInd]){
if(chd == par)
continue;
depthMinDif(chd,nodeInd);
}
}
}```