Submission #2660793

---

Source Code Expand

# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(1000000)

class Solver():

    def __init__(self):
        N = int(input())
        self.G = [[] for _ in range(N + 1)]
        self.B = [0] * (N+1)
        self.W = [0] * (N+1)
        self.T = [0] * (N+1)
        self.MOD = 10**9 + 7

        for _ in range(N-1):
            a, b = map(int, input().split())
            self.G[a].append(b)
            self.G[b].append(a)

    def total(self, pre, now):
        if self.T[now] == 0:
            self.T[now] = (self.black(pre, now) + self.white(pre, now) )% self.MOD
        return self.T[now]

    def black(self, pre, now):
        if self.B[now] == 0:
            tmp = 1
            for post in self.G[now]:
                if post == pre:
                    continue
                tmp = (tmp * self.white(now, post)) % self.MOD
            self.B[now] = tmp
        return self.B[now]

    def white(self, pre, now):
        if self.W[now] == 0:
            tmp = 1
            for post in self.G[now]:
                if post == pre:
                    continue
                tmp = (tmp * self.total(now, post)) % self.MOD
            self.W[now] = tmp
        return self.W[now]


if __name__ == "__main__":
    S = Solver()
    print(S.total(None, 1))

Submission Info

Judge Result