К Урттай Дэд Модны Тоо

Сайн байцгаана уу.
Саяхан кодефорсес дээр болсон нэг тэмцээнд ирсэн модны бодлогын бодолтоо сонирхуулья.

Бодлого:

Өгөгдсөн модонд яг К урттай бүх дэд модны тоог ол. Модны орой 50000-аас хэтрэхгүй К нь 500-аас хэтрэхгүй.

Бодолт:

За ер нь модны бодлого ихэвчлэн Divide and Conquer, dp байдаг. Модны бодлогыг бодохдоо дурын оройгоос нь өлгөөд Rooted Tree болгож төсөөлөх хэрэгтэй. Аль ч оройгоос өлгөхөд модны чанар өөрчлөгдөхгүй. Тэгээд мэдээж Рекурсыг маш сайн ойлгож, эзэмшсэн байх ёстой.

dp[i][j]-ээр i орой дээр эхлэлтэй j урттай бүх дэд модны тоог тэмдэглэвэл хариу:

SUM( dp[i][k-j-1]*dp[u][j] ) энд i=1..N бүх орой, j=1..K, u= i-р оройн бүх хөрш орой. dp-ээ тэмдэглэхдээ анхаарах зүйл А Б гэсэн хөрш оройг тэмдэглэсэн бол Б А-г дахин тооцох ёсгүйг анхаараарай. Рекурсив функцыг доор сонирхуулья.

void dfs(int child, int dad){
    for(int i=0; i<v[child].size(); i++){
        int u = v[child][i];
        if(u==dad)continue;
        dfs(u, child);
        for(int j=0; j<k; j++)
           ret += (long long)( dp[child][k-j-1]*dp[u][j] );
        for(int j=0; j<k; j++)
           dp[child][j+1] += dp[u][j];
    }
}