daily 2

CF 855C

int dp[N][K][3];//dp[i][j][k] means using j colors in i's subtrees and k=0/1/2 indicates the current one is less/equal/greater than k
int cur[N][K];
int main(){
    int n,m,k,X;
    cin>>n>>m;
    vector<vector<int>>E(n+1);
    for(int i=1;i<=n-1;++i){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    cin>>k>>X;
    vector<int>sz(n+1);
    function<void(int,int)>dfs=[&](int x,int f){
        sz[x]=1;
        dp[x][0][0]=k-1;
        dp[x][1][1]=1;
        dp[x][0][2]=m-k;
        for(int v:E[x]){
            if(v==f)continue;
            dfs(v,x);
            int lim1=min(sz[x],X),lim2;
            for(int i=0;i<=lim1;++i){
                for(int j=0;j<=2;++j){
                    cur[i][j]=dp[x][i][j];
                    dp[x][i][j]=0;
                }
            }
            for(int i=0;i<=lim1;++i){
                lim2=min(X-i,sz[v]);
                for(int j=0;j<=lim2;++j){
                    dp[x][i+j][0]=(dp[x][i+j][0]+(1ll*cur[i][0]*((dp[v][j][0]+dp[v][j][1])%MOD+dp[v][j][2])%MOD))%MOD;
                    dp[x][i+j][1]=(dp[x][i+j][1]+(1ll*cur[i][1]*((dp[v][j][0]))%MOD))%MOD;
                    dp[x][i+j][2]=(dp[x][i+j][2]+(1ll*cur[i][2]*((dp[v][j][0]+dp[v][j][2]))%MOD)%MOD)%MOD;
                }
            }
            sz[x]+=sz[v];
        }
    };
    dfs(1,0);
    ll ans=0;
    for(int i=0;i<=X;++i){
        for(int j=0;j<=2;++j){
            ans=(ans+dp[1][i][j])%MOD;
        }
    }
    cout<<ans<<'\n';
}

CF 1015E2

int main(){
    int n,m;
    cin>>n>>m;
    vector mp(n+1,vector<int>(m+1)),mark(mp),sz(mp);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            char c;
            cin>>c;
            mp[i][j]=(c=='*');
        }
    }
    auto check=[&](int x,int y,int k){
        return (x-k)&&(x+k)<=n&&(y-k)&&(y+k)<=m&&mp[x+k][y]&&mp[x-k][y]&&mp[x][y+k]&&mp[x][y-k];
    };
    int ans=0;
    for(int i=2;i<n;++i){
        for(int j=2;j<m;++j){
            if(!mp[i][j]||!mp[i-1][j]||!mp[i][j-1]||!mp[i][j+1]||!mp[i+1][j]){//do not do non-center point again
                continue;
            }
            mark[i][j]=1;
            int len=1;
            for(;check(i,j,len);len++){
                mark[i-len][j]=mark[i+len][j]=mark[i][j+len]=mark[i][j-len]=1;
            }
            sz[i][j]=len-1;
            ++ans;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(mp[i][j]&&!mark[i][j]){
                cout<<-1<<'\n';
                return 0;
            }
        }
    }
    cout<<ans<<'\n';
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(sz[i][j]){
                cout<<i<<' '<<j<<' '<<sz[i][j]<<'\n';
            }
        }
    }
    return 0;
}