[DP] LOJ#2473. '9성 연합고사 2018'비밀습격

fi f i를 설정하면 선택한 연결 블록의 kk가 i와 같은 방안수보다 크다는 것을 나타낸다
그럼 정답은 ∑wi=1i (fi -3-fi+1) = ∑wi=1fi∑i = 1 w i (f i -3 f i + 1) = ∑i = 1 w f i
ii를 일일이 열거하여 권한이 ii보다 큰 점을 1 1로 표시하고 그렇지 않으면 0 0으로 표시한다.fi fi는 나무에 최소한 k k 개 1 의 연결 블록을 포함하는 개수이다.나무형DP를 누르면 된다
이렇게 복잡도는 O(n3)O(n3)인데 시한이 이렇게 많으면 틀림없어...

#include 
#include 
#include 

using namespace std;

typedef long long ll;

const int N=2010,P=64123;

int n,m,w,cnt,G[N],b[N],a[N],size[N],f[N][N];
struct edge{
    int t,nx;
}E[N<<1];

inline void addedge(int x,int y){
    E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt;
    E[++cnt].t=x; E[cnt].nx=G[y]; G[y]=cnt;
}

inline void dp(int x,int p){
    size[x]=b[x];
    int *F=f[x];
    for(int j=0;j<=n;j++) f[x][j]=0;
    F[b[x]]=1;
    for(int i=G[x];i;i=E[i].nx)
        if(E[i].t!=p){
            dp(E[i].t,x);
            static ll tmp[N]; int *G=f[E[i].t];
            for(int j=0;j<=size[x]+size[E[i].t];j++) tmp[j]=F[j];
            for(int j=0;j<=size[x];j++)
                for(int k=0;k<=size[E[i].t];k++)
                    tmp[j+k1LL*F[j]*G[k];
            size[x]+=size[E[i].t]; size[x]=size[x]for(int j=0;j<=size[x];j++) F[j]=tmp[j]%P;
        }
}

int main(){
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,x,y;iscanf("%d%d",&x,&y),addedge(x,y);
    int ans=0,lst=0,lstans=0;
    for(int i=1;i<=w;i++){
        int tot=0;
        for(int j=1;j<=n;j++) b[j]=(a[j]>=i),tot+=b[j];
        if(totcontinue;
        if(tot==lst){
            ans=(ans+lstans)%P; continue;
        }
        lst=tot; lstans=0;
        dp(1,0);
        for(int j=1;j<=n;j++)
            lstans=(lstans+f[j][m])%P;
        ans=(ans+lstans)%P;
    }
    printf("%d
",ans);
    return 0;
}