Tree

题意：
给与一棵n个节点的树，求每个点的连通点集的数量？

思路：
树形结构+换根
dp[i]表示以i为根且包括i的这棵子树连通点集的数量。
ans[i]表示包括i的连通点集的数量，既结果。
父节点u与子节点v：
dp[u]= (dp[v]+1) * dp[u];（v为u的子节点）
换根时:
ans[v]=((ans[u]/(dp[v]+1))+1)*dp[v];
注意：0不能求逆元，所以当(dp[v]+1)%inf=0时，你就需要重新计算一下该点的结果。

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=1e9+7;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll dp[1000005], ans[1000005];

vector<int> g[1000005];

void dfs(int v, int f)
{
    dp[v]=1;
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            dfs(g[v][i],v);
        }
        else
        {
            continue;
        }
        dp[v]=((dp[g[v][i]]+1)*dp[v])%inf;
    }
}

ll fun(ll n,ll m)
{
   ll s=1;
   while(m)
   {
       if(m&1)
       {
           s=s*n%inf;
       }
       n=n*n%inf;
       m=m/2;
   }
   return s;
}

void dfs1(int v, int f)
{
    if(f!=-1)
    {
        if((dp[v]+1)%inf==0)
        {
            dfs(v,-1);
            ans[v]=dp[v];
        }
        else
        {
            ans[v]=((ans[f]*fun((dp[v]+1),inf-2)%inf)+1)*dp[v]%inf;
        }
    }
    else
    {
        ans[v]=dp[v];
    }
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            dfs1(g[v][i],v);
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int u=read(), v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,-1);
    dfs1(1,-1);
    for(int i=1;i<=n;i++)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}