DDCC 2017 D. なめらかな木

D: なめらかな木 - DISCO presents ディスカバリーチャンネルコードコンテスト2017 本戦 | AtCoder

解法

bitDPをする

実装

#include "bits/stdc++.h"
using namespace std;

const int MOD = 1000000007;

int n;
vector<int> g[55];
map<tuple<long long, int, int>, long long> dp;

long long dfs(long long s, int prev, int pprev) {
        if (__builtin_popcountll(s) == n) return 1;
        for (int x = 0; x < n; x ++) {
                for (auto y : g[x]) {
                        if (x == prev || x == pprev) continue;
                        if (y == prev || y == pprev) continue;
                        bool used1 = (s & (1LL << x)) != 0;
                        bool used2 = (s & (1LL << y)) != 0;
                        if (used1 != used2) return 0;
                }
        }
        auto key = tuple<long long, int, int> (s, prev, pprev);
        if (dp.count(key)) return dp[key];
        long long sum = 0;
        for (int x = 0; x < n; x ++) {
                if (s & (1LL << x)) continue;
                sum += dfs(s | (1LL << x), x, prev);
        }
        return dp[key] = sum % MOD;
}

int main() {
        scanf("%d", &n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        for (int i = 0; i < n; i ++) if (g[i].size() > 4) return !puts("0");
        printf("%lld\n", dfs(0, -1, -1));
        return 0;
}