Submission #924259
Source Code Expand
import java.util.*; import java.util.function.BiFunction; public class Main { Scanner sc = new Scanner(System.in); public static void main(String[] args) { new Main().run(); } class Node { ArrayList<Node> list = new ArrayList<>(); ArrayList<Node> adj = new ArrayList<>(); int id; int depth; Node(int i) { id = i; } } long MOD = 1_000_000_007; long[] memoF; long f(Node node) { if (memoF[node.id] != 0) { return memoF[node.id]; } long white = g(node); long black = 1; for (Node c : node.list) { black *= g(c); black %= MOD; } long sum = white + black; sum %= MOD; memoF[node.id] = sum; // debug("f", node.id, sum); return sum; } long[] memoG; long g(Node node) { if (memoG[node.id] != 0) { return memoG[node.id]; } long white = 1; for (Node c : node.list) { white *= f(c); white %= MOD; } // debug("g", node.id, white); memoG[node.id] = white; return white; } void make(Node node, int n) { boolean[] done = new boolean[n + 1]; done[node.id] = true; Queue<Node> queue = new LinkedList<>(); queue.add(node); node.depth = 0; while (queue.size() > 0) { Node atom = queue.poll(); for (Node next : atom.adj) { if (done[next.id]) { continue; } done[next.id] = true; atom.list.add(next); queue.add(next); next.depth = atom.depth + 1; } } } void run() { int n = ni(); ArrayList<Node> list = new ArrayList<>(); for (int i = 0; i < n + 1; ++i) { list.add(new Node(i)); } for (int i = 0; i < n - 1; ++i) { int u = ni(); int v = ni(); list.get(u).adj.add(list.get(v)); list.get(v).adj.add(list.get(u)); } make(list.get(1), n); memoF = new long[n + 1]; memoG = new long[n + 1]; PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> b.depth - a.depth); for (int i = 1; i <= n; ++i) { queue.add(list.get(i)); } while (queue.size() > 0) { Node node = queue.poll(); f(node); } System.out.println(memoF[1]); } int ni() { return Integer.parseInt(sc.next()); } void debug(Object... os) { System.err.println(Arrays.deepToString(os)); } class BIT<T> { int n; ArrayList<T> bit; BiFunction<T, T, T> bif; BIT(int n, BiFunction<T, T, T> bif, T defaultValue) { this.n = n; bit = new ArrayList<>(n + 1); for (int i = 0; i < n + 1; ++i) { bit.add(defaultValue); } this.bif = bif; } void update(int i, T v) { for (int x = i; x <= n; x += x & -x) { bit.set(x, bif.apply(bit.get(x), v)); } } T reduce(int i, T defaultValue) { T ret = defaultValue; for (int x = i; x > 0; x -= x & -x) { ret = bif.apply(ret, bit.get(x)); } return ret; } } }
Submission Info
Submission Time | |
---|---|
Task | D - 塗り絵 |
User | arukuka |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 3106 Byte |
Status | AC |
Exec Time | 981 ms |
Memory | 73772 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
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 | 231 ms | 14800 KB |
001.txt | AC | 209 ms | 14540 KB |
002.txt | AC | 809 ms | 60848 KB |
003.txt | AC | 923 ms | 72088 KB |
004.txt | AC | 786 ms | 61308 KB |
005.txt | AC | 971 ms | 71752 KB |
006.txt | AC | 881 ms | 70636 KB |
007.txt | AC | 922 ms | 73772 KB |
008.txt | AC | 799 ms | 62260 KB |
009.txt | AC | 898 ms | 72332 KB |
010.txt | AC | 840 ms | 61440 KB |
011.txt | AC | 869 ms | 72448 KB |
012.txt | AC | 719 ms | 54868 KB |
013.txt | AC | 902 ms | 73736 KB |
014.txt | AC | 651 ms | 41004 KB |
015.txt | AC | 903 ms | 72584 KB |
016.txt | AC | 775 ms | 61920 KB |
017.txt | AC | 921 ms | 71920 KB |
018.txt | AC | 524 ms | 33532 KB |
019.txt | AC | 981 ms | 70836 KB |
020.txt | AC | 427 ms | 26164 KB |
021.txt | AC | 977 ms | 73560 KB |