原题链接：
Kingdom Division
- 由于树的层次可能很深，所以这里不能使用递归版的DFS。我使用了BFS。
- BFS确定各结点的父结点和它的孩子数。
- 用逆拓扑排序确定结点的计算顺序。
- same[u][] 表示u结点颜色为0孩子结点颜色全为1时组合数。 diff[u][] 表示u结点颜色为0时可行组合数。本结点颜色为0，子结点颜色为1，孙结点颜色全为0是无效组合。反之亦然。由于这里颜色0、1相互对称， same[u][]=same[u][]; diff[u][]=diff[u][]; 。
- 为排除无效组合，计算 diff[u][] 时没有乘以 same[u][] 。
- 本结点为0，孩子结点全为1，是无效组合，因此 diff[u][] 最后还要减去 same[u][] 。
#include <cmath>
#include <cstdio>
#include <cassert>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MOD = 1e9+;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n = ; assert( == scanf("%d", &n));
vector<vector<int>> adjList(n + );
for(int i = ; i < n - ; i++){
int u, v; assert( == scanf("%d %d", &u, &v));
adjList[u].push_back(v);
adjList[v].push_back(u);
}
vector<vector<long long>> diff(n + , vector<long long>(, ));
vector<vector<long long>> same(n + , vector<long long>(, ));
vector<int> parent(n + , );
vector<int> child_cnt(n + , );
queue<int> traversal_array;
vector<bool> visited(n + , false);
traversal_array.push();
visited[] = true;
while(!traversal_array.empty()){
int tmp = traversal_array.front();
traversal_array.pop();
for(auto vit: adjList[tmp]){
if(!visited[vit]){
visited[vit] = true;
child_cnt[tmp]++;
parent[vit] = tmp;
traversal_array.push(vit);
}
}
} for(int c_i = ; c_i <= n; c_i++){
if(!child_cnt[c_i]){
traversal_array.push(c_i);
}
} while(!traversal_array.empty()){
int tmp = traversal_array.front();
traversal_array.pop();
child_cnt[parent[tmp]]--;
if(child_cnt[parent[tmp]] == ){
traversal_array.push(parent[tmp]);
}
for(auto vit: adjList[tmp]){
if(vit != parent[tmp]){
same[tmp][] = same[tmp][] * diff[vit][] % MOD;
same[tmp][] = same[tmp][] * diff[vit][] % MOD;
}
}
for(auto vit: adjList[tmp]){
if(vit != parent[tmp]){
diff[tmp][] = diff[tmp][] * (diff[vit][] + diff[vit][] + same[vit][]) % MOD;
diff[tmp][] = diff[tmp][] * (diff[vit][] + diff[vit][] + same[vit][]) % MOD;
}
}
diff[tmp][] = (diff[tmp][] - same[tmp][] + MOD) % MOD;
diff[tmp][] = (diff[tmp][] - same[tmp][] + MOD) % MOD;
}
printf("%lld\n", (diff[][] + diff[][])%MOD);
return ;
}