C Tree

题目地址：

https://ac.nowcoder.com/acm/contest/6226/C

基本思路：

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
inline int qsm(int x,int n){
  int res = 1;
  while (n){
    if(n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
int n;
struct Edge{
    int to,next;
}edge[maxn << 1];
int cnt = 0 ,head[maxn];
void add_edge(int u,int v){
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  head[u] = cnt;
}
int dp[maxn],fa[maxn];
void dfs1(int u,int par){
  dp[u] = 1; fa[u] = par;
  for(int i = head[u] ; i != -1 ;i = edge[i].next) {
    int to = edge[i].to;
    if (par == to) continue;
    dfs1(to,u);
    dp[u] = dp[u]  * (dp[to] + 1) % mod;
  }
}
int memo[maxn],ans[maxn];
void dfs2(int u,int par) {
  if (u != 1) {
    if ((dp[u] + 1) % mod) { // 不为0直接求逆元;
      memo[u] = ans[par] * qsm(dp[u] + 1LL, mod - 2) % mod;
      ans[u] = dp[u] * (1LL + memo[u]) % mod;
    } else {
      //这部分和dfs1里的dp过程是一样的，只是将子树反向了。
      int tmp = memo[par] + 1;
      for (int i = head[par]; i != -1; i = edge[i].next) { 
        int to = edge[i].to;
        if (to != u && to != fa[par]) tmp = tmp * (dp[to] + 1) % mod;
      }
      memo[u] = tmp;
      ans[u] = (tmp + 1) * dp[u] % mod;
    }
  }
  for (int i = head[u]; i != -1; i = edge[i].next) {
    int to = edge[i].to;
    if (to == par) continue;
    dfs2(to,u);
  }
}
signed main() {
  n = read();
  cnt = 0; mset(head,-1);
  rep(i,1,n - 1) {
    int u = read(), v = read();
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs1(1,0);
  ans[1] = dp[1];
  dfs2(1,0);
  rep(i,1,n) printf("%lld\n",ans[i]);
  return 0;
}