Source Code

Problem: 3140  User: yzhw 
Memory: 5480K  Time: 704MS 
Language: Java  Result: Accepted 

Source Code 
import java.io.*;
import java.util.Arrays;
public class Main {
	static final int N=100001;
	static long size[]=new long[N];
    static int g[]=new int[N];
    static int next[]=new int[2*N],v[]=new int[2*N],c=0;
    static long dfs(int pos,int fa)
    {
    	for(int p=g[pos];p!=-1;p=next[p])
    		if(v[p]!=fa)
    			size[pos]+=dfs(v[p],pos);
    	return size[pos];
    }
	public static void main(String[] args) throws IOException{
	      StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	      int n=0,m=0,count=1;      
	      while(true)
	      {
	    	  in.nextToken();n=(int)in.nval;
	    	  in.nextToken();m=(int)in.nval;
	    	  if(n==0&&m==0) break;
	    	  Arrays.fill(g,-1);
	    	  c=0;
	    	  for(int i=1;i<=n;i++)
	    	  {
	    		  in.nextToken();size[i]=(long)in.nval;
	    	  }
	    	  while((m--)!=0)
	    	  {
	    		  int a,b;
	    		  in.nextToken();a=(int)in.nval;
		    	  in.nextToken();b=(int)in.nval;
		    	  v[c]=b;next[c]=g[a];g[a]=c++;
		    	  v[c]=a;next[c]=g[b];g[b]=c++; 
	    	  }
	    	  dfs(1,1);
	    	  long minnum=size[1];
	    	  for(int i=2;i<=n;i++)
	    		  minnum=Math.min(minnum,Math.abs(size[1]-size[i]-size[i]));
	    	  System.out.println("Case "+(count++)+": "+minnum);	    		  
	      }
	}
}