[JZOJ4599] 서행요괴.

Description

환상의 고향 백옥루에는 일년 내내 꽃이 피지 않는 벚나무 한 그루가 있는데 서행요괴라고 한다. 서행사 유유자는 꽃을 피우기 위해 봄을 대량으로 수집하다가 성관에 혼이 났다. 지금은 유유자가 성관의 허락을 받아 S점춘도를 수집하여 서행요괴에게 다시 꽃을 피우게 한다.서행요괴는 n개의 노드가 있는 나무로 볼 수 있는데 각 잎의 노드마다 1시의 봄이 분배되면 꽃이 핀다(유유자는 무의식적으로 그녀의 봄을 사용하지 않기 때문에 최대 한 잎의 노드에 1시의 봄만 분배된다). 비잎의 노드 i에 대해 적어도 한 명의 아들이 꽃을 피운다면 노드 i는 꽃이 핀다.서행요괴의 꽃이 만개하면 유유자가 부활한다고 한다.하지만 도시관리는 S점춘도(S≤20)만 줬기 때문에 유유자는 이번에는 오락적인 마음으로 나무를 심었다.만약 서행요괴가 적어도 m개의 노드에서 꽃을 피운다면 유유자는 그것이 아름답다고 생각한다.현재 유유자는 서행요괴를 아름답게 하는 방안이 얼마나 많은지 알고 싶어한다(답은 10^9+7에 대한 모범이다).주의: 유유자가 반드시 S점의 춘도를 다 분배하는 것은 아니다.

Solution

딱 봐도 DP 문제예요.

f[i][j][k]를 설정하면 i번째 잎 노드에 j개의 봄을 사용했고 k개의 노드가 꽃을 피워 전이한 것이 분명하다. f[i][j][k]=∑f[l][j-1][k-(deep[i]-3 deep[lca(i,l)]]]는 잎 노드가 어지럽히면 DP에 영향을 줄 수 있기 때문에 잎 노드는 dfs순으로 순서를 정하는 것이 가장 좋다.O(n3s)70점

최적화

만약 직접 dfs 순서의 순서로 이동한다면, 하위 나무의lca의 깊이는 점차 증가할 것이다.이 성질을 활용하여 쉽게 이동할 수 있도록 s[j][k][d]=∑f[l][j][k], d는 모든lca(i,l)의 깊이가 d임을 나타낸다. s만으로는 이동할 수 없다. 방정식을 관찰하고 cnt[j][k-d]=∑s[j][k][d]를 설정하면 f[i][j][k]=cnt[j-1][k-3ep[i]]는 잎마다 방문할 때 갱신하고 cnf와 cnt를 업데이트한다.매번 i의 모든 하위 노드를 검색하고 위로 전달한 후에 원래lca의 깊이는 d였는데 지금은 d-1이 되었다. 모든 것은 s[j][k][d-1]의 값을 업데이트하고 s[i][]j[d]를 비우고 cnt 그룹을 계속 업데이트해야 한다.

운전사 춘도가 뭐야?

xdl: 몰라요.

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
#define rep(i,a) for(i=first[a];i;i=next[i])
using namespace std;
const int maxn=1007,mo=1000000007;
int i,j,k,l,t,n,m,s;
bool bz[maxn];
int last[maxn*2],first[maxn*2],next[maxn*2],num,ans;
int f[maxn][22][maxn],deep[maxn],df[maxn],a[maxn],dfn,pp;
int cnt[maxn][maxn*2],ss[22][maxn][maxn],tot;
struct node{
    int x,y;
}b[maxn];
bool cmp(node x,node y){
    return x.y<y.y;
}
void add(int x,int y){
    last[++num]=y,next[num]=first[x],first[x]=num;
}
int lca(int x,int y){
    int i,j;
    if(deep[x]<deep[y])swap(x,y);
    fod(i,20,0)if(deep[f[x][i][j]]>deep[y])x=f[x][i][j];
    if(deep[x]!=deep[y])x=f[x][0][j];
    fod(i,20,0)if(f[x][i][j]!=f[y][i][j])x=f[x][i][j],y=f[y][i][j];
    if(x!=y)return f[x][0][j];return x;
}
void dfs(int x,int y){
    int i,j;
    deep[x]=deep[y]+1;
    rep(i,x)if(last[i]!=y)dfs(last[i],x);
    if(!first[x]){
        ++tot;
        fo(i,1,s){
            fo(j,deep[x],n)(f[tot][i][j]=cnt[i-1][j-deep[x]])%=mo;  
        }
        fo(i,1,s){
            fo(j,1,n)if(f[tot][i][j])(ss[i][j][deep[x]]+=f[tot][i][j])%=mo;
        }
        fo(i,1,s){
            fo(j,deep[x],n)if(f[tot][i][j])(cnt[i][j-deep[x]]+=f[tot][i][j])%=mo;
        }
    }
    fo(i,1,s){
        fo(j,deep[x],n)if(ss[i][j][deep[x]]){
            (cnt[i][j-deep[x]]-=ss[i][j][deep[x]])%=mo;
            (cnt[i][j-deep[x]+1]+=ss[i][j][deep[x]])%=mo;
        }
    }
    fo(i,1,s){
        fo(j,1,n)if(ss[i][j][deep[x]]){
            (ss[i][j][deep[x]-1]+=ss[i][j][deep[x]])%=mo;
            ss[i][j][deep[x]]=0;
        }
    }
}
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    fo(i,2,n)scanf("%d",&k),add(k,i);cnt[0][0]=1;
    dfs(1,0);
    fo(i,1,tot)fo(j,1,s)fo(k,m,n)if(f[i][j][k])ans=(ans+f[i][j][k])%mo;
    printf("%d
",ans);
}