정점이 N개인 트리가 주어진다. 동철이는 각 정점을 검은색 아니면 하얀색 중 하나로 칠하려고 한다. 단, 어떤 간선으로 연결된 두 정점이 모두 검은색이면 안 된다. 색칠하는 것으로 가능한 경우의 수는 몇 가지인가?
예를 들면 아래와 같은 트리가 있다고 하면
가능한 모든 색칠의 경우의 수는
(하얀색/하얀색), (하얀색/검은색), (검은색/하얀색), (검은색/검은색)
[(1번정점의색/2번정점의색)]이지만, 위 조건을 만족하는 경우의 수는 (검은색/검은색)을 제외한 나머지 3개이다.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(2≤N≤100,000)이 주어진다.
다음 N-1개의 줄의 각 줄에는 두 정수 x,y(1 ≤ x < y ≤ N)
[출력]
각 테스트 케이스마다 ‘#t’를 찍고 하나의 빈 칸으로 구분하여, 트리의 각 정점을 색칠할 수 있는 경우의 수를 출력한다. 이 수는 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력하도록 한다. (t는 테스트 케이스 번호이며, 1부터 시작한다.)
입력 예제
출력 예제
2 // 테스트 케이스 개수
2 // 첫 번째 테스트 케이스 N
1 2 // x, y
5 // 두 번째 케이스 N
1 3 // x1, y1,
2 3 // x2, y2
3 4 // x3, y3
4 5 // x4, y4
#1 3
#2 14
#include <stdio.h>#include <malloc.h>#define MAX 100000#define MOD 1000000007enum { W, B };typedef long long LL;typedef struct _EDGE { int idx; struct _EDGE* next;} EDGE;typedef struct { int chk; EDGE* edge;} VRTX;int N, Ei;VRTX V[MAX + 1];EDGE E[MAX * 2 + 1];LL D[MAX + 1][2];void add_edge(int from, int to){ E[Ei].idx = to; E[Ei].next = V[from].edge; V[from].edge = &E[Ei++];}LL calc(int idx, int WB){ if (D[idx][WB] == -1) { LL ret = 1; EDGE* cur = V[idx].edge; V[idx].chk = 1; while (cur) { if (!V[cur->idx].chk) if (WB == W) ret = ret * ((calc(cur->idx, W) + calc(cur->idx, B)) % MOD) % MOD; else ret = ret * calc(cur->idx, W) % MOD; cur = cur->next; } V[idx].chk = 0; D[idx][WB] = ret; } return D[idx][WB];}int main(void){ int TC, from, to; scanf("%d", &TC); for (int tc = 1; tc <= TC; tc++) { scanf("%d", &N); Ei = 0; for (int i = 1; i <= N; i++) { V[i].chk = V[i].edge = 0; D[i][W] = D[i][B] = -1; } for (int i = 1; i < N; i++) { scanf("%d %d", &from, &to); add_edge(from, to); add_edge(to, from); } printf("#%d %lld\n", tc, (calc(1, W) + calc(1, B)) % MOD); } return 0;} |