Loading...

洛谷P2796 Facer的程序

check评论:0 条 remove_red_eye浏览量:303 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-17

qwq...很简单的$dp$

我们设$dp[i]$表示以$i$为根的树中包含了$i$的方案数

那么从下往上推一次就好qwq...

#include <bits/stdc++.h>
using namespace std;
#define mod (int)(1e9+7)
#define ll long long
int n,cnt;
int head[100010];
ll f[100010],ans;
struct edge
{
    int next,to;
}e[200020];
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void pushup(ll &a,ll b) 
{
    a=a*(b+1)%mod;
}
void dfs(int u,int fa)
{
    f[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)
        {
            continue;
        }
        dfs(v,u);
        pushup(f[u],f[v]);
    } 
    ans+=f[u];
    ans%=mod;
} 
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,1);
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名