卡常求助

回复帖子

@zero4338  2020-01-16 08:11 回复

t最后一个点

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+10;
const int p=1e9+7;
int n,k;
int head[maxn],ver[maxn<<1],nxt[maxn<<1];
int tot;
inline void add(int x,int y)
{
    ver[++tot]=y;nxt[tot]=head[x];
    head[x]=tot;
}
int f[maxn][105][2][2],g[maxn][2][2];
int siz[maxn];
inline void dfs(int u,int fa)
{
    f[u][0][0][0]=f[u][1][1][0]=1;
    siz[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,u);
        for(int j=0;j<=k;j++)
        {
            g[j][0][0]=f[u][j][0][0];f[u][j][0][0]=0;
            g[j][0][1]=f[u][j][0][1];f[u][j][0][1]=0;
            g[j][1][0]=f[u][j][1][0];f[u][j][1][0]=0;
            g[j][1][1]=f[u][j][1][1];f[u][j][1][1]=0;
        }
        for(int j=0;j<=min(siz[u],k);j++)
        {
            for(int m=0;m<=min(siz[y],k-j);m++)
            {
                f[u][j+m][0][0]=(f[u][j+m][0][0]+1ll*g[j][0][0]*f[y][m][0][1]%p)%p;
                f[u][j+m][0][1]=(f[u][j+m][0][1]+1ll*(g[j][0][1]+g[j][0][0])%p*f[y][m][1][1])%p;
                f[u][j+m][0][1]=(f[u][j+m][0][1]+1ll*g[j][0][1]*f[y][m][0][1]%p)%p;
                f[u][j+m][1][0]=(f[u][j+m][1][0]+1ll*g[j][1][0]*(f[y][m][0][0]+f[y][m][0][1])%p)%p;
                f[u][j+m][1][1]=(f[u][j+m][1][1]+1ll*g[j][1][1]*(f[y][m][0][0]+f[y][m][0][1])%p)%p;
                f[u][j+m][1][1]=(f[u][j+m][1][1]+1ll*(g[j][1][0]+g[j][1][1])%p*(f[y][m][1][0]+f[y][m][1][1])%p)%p;
            }
        }
        siz[u]+=siz[ver[i]];
    }
}
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;
    for(;ch<='9'&&ch>='0';ch= getchar())s=s*10+ch-'0';
    return s*w;
}
int main()
{
    n=read();k=read();
    for(int i=1;i<=n-1;i++)
    {
        int x,y;x=read();y=read();
        add(x,y);add(y,x);
    }
    dfs(1,1);
    int ans=(f[1][k][0][1]+f[1][k][1][1])%p;
    printf("%d\n",ans);
    return 0;
}
@Piwry 2020-08-31 10:29 回复 举报

@zero4338

试试用 vector

然后观察数据,n 远大于 k,如果树太深答案一定是 0,出题人可能不想让输出 0的人拿高分,那么这颗树节点的度数大概率非常大,近似一个菊花图。 这时再写链表显然是不明智的做法,利用vector内存连续的特性,一般情况下比链表要快了。就不会出现提交记录里面的一片 80 分,开O2后 100 分的尴尬情况。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。