Submission #1294285


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];
			ff*=g[e.to];
			gg%=mod;
			ff%=mod;
		}
		ff+=(gg%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

Submission Time
Task D - 塗り絵
User kwkm0429
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 1177 Byte
Status AC
Exec Time 642 ms
Memory 107132 KB

Compile Error

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

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 22
Set Name Test Cases
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt
Case Name Status Exec Time Memory
000.txt AC 93 ms 21716 KB
001.txt AC 93 ms 21076 KB
002.txt AC 560 ms 74096 KB
003.txt AC 639 ms 103596 KB
004.txt AC 539 ms 71060 KB
005.txt AC 642 ms 104800 KB
006.txt AC 604 ms 92788 KB
007.txt AC 621 ms 103784 KB
008.txt AC 537 ms 72232 KB
009.txt AC 620 ms 106776 KB
010.txt AC 542 ms 70764 KB
011.txt AC 621 ms 104064 KB
012.txt AC 505 ms 68420 KB
013.txt AC 635 ms 104308 KB
014.txt AC 452 ms 66100 KB
015.txt AC 633 ms 107132 KB
016.txt AC 524 ms 69160 KB
017.txt AC 608 ms 104856 KB
018.txt AC 317 ms 44412 KB
019.txt AC 624 ms 102608 KB
020.txt AC 251 ms 45908 KB
021.txt AC 621 ms 105424 KB