Submission #924303


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;

    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);
    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);
      }
    }
  }

  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];
    long ans = f(list.get(1));
    System.out.println(ans);
  }

  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 2815 Byte
Status AC
Exec Time 813 ms
Memory 70580 KB

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 129 ms 9556 KB
001.txt AC 129 ms 9556 KB
002.txt AC 654 ms 59528 KB
003.txt AC 745 ms 70008 KB
004.txt AC 640 ms 59372 KB
005.txt AC 781 ms 70360 KB
006.txt AC 703 ms 61268 KB
007.txt AC 735 ms 70368 KB
008.txt AC 646 ms 59848 KB
009.txt AC 813 ms 70580 KB
010.txt AC 630 ms 60148 KB
011.txt AC 747 ms 70128 KB
012.txt AC 579 ms 50032 KB
013.txt AC 729 ms 70124 KB
014.txt AC 548 ms 39220 KB
015.txt AC 756 ms 69736 KB
016.txt AC 574 ms 50508 KB
017.txt AC 695 ms 61576 KB
018.txt AC 359 ms 32676 KB
019.txt AC 738 ms 69556 KB
020.txt AC 310 ms 23300 KB
021.txt AC 754 ms 69776 KB