Submission #1294278

---

Source Code Expand

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().solve();
	}
	
	int N;
	Long[] f; //iを根として塗れる数
	Long[] g; //iが白で根として塗れる数
	List<Edge>[] edge;
	int mod=(int)Math.pow(10, 9)+7;
	boolean used[];
	
	void solve(){
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		f=new Long[N];
		g=new Long[N];
		edge=new List[N];
		used=new boolean[N];
		for(int i=0;i<N;i++)edge[i]=new ArrayList<Edge>();
		
		for(int i=0;i<N-1;i++){
			int a=sc.nextInt()-1;
			int b=sc.nextInt()-1;
			addEdge(a,b);
			addEdge(b,a);
		}
		
		dfs(0);
		System.out.println(f[0]);
	}
	void dfs(int s){
		used[s]=true;
		long gg=1;
		long ff=1;
		for(Edge e:edge[s]){
			if(used[e.to])continue;
			dfs(e.to);
			gg*=f[e.to]%mod;
			ff*=g[e.to]%mod;
			gg%=mod;
			ff%=mod;
		}
		ff+=(gg%mod);
		ff%=mod;
		g[s]=gg%mod;
		f[s]=ff%mod;
	}
	void addEdge(int from,int to){
		edge[from].add(new Edge(to,from));
	}
	
	class Edge{
		int to;
		int from;
		Edge(int to,int from){
			this.to=to;
			this.from=from;
		}
	}
}

Submission Info

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result