题解 CF762F [Tree nesting]

· · 题解

Link

唯一的一篇洛谷题解说的不是很清楚，让我来说清楚一点。你还可以参考大象的题解。

这是一道比较麻烦的树形+状压DP。

我们把S的根当作0（我从0开始计数），枚举T的根。

我们设f_{s,t,i}，表示S中s与T中t匹配，其中T的，已被匹配的儿子集合是i的方案数。枚举S的一个儿子a，枚举他是否匹配，匹配到了t上的哪一个儿子。

初始值： f_{s,t,\emptyset}=1

转移：

f_{s,t,i}\leftarrow f_{s,t,i-\{u\}}ans_{a,son[t][u]}

其中ans_{s,t}=f_{s,t,U},U表示t儿子的全集。

全局ans += \sum_{b,a}ans_{b,a}

DP的复杂度是O(ST^22^T)，用记忆化搜索实现，显然跑不满。

然而这样肯定算重复，根据某个我不知道的结论，算重复的次数恰好是T与T自我匹配匹配的方案数，所以除掉就好了。

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

const int mod = 1e9 + 7 , N = 1000 , M = 12;
inline void add(int &x , int y) {x += y ; if(x >= mod) x -= mod;}
inline void sub(int &x , int y) {x -= y ; if(x < 0) x += mod;}

struct Tree : vector<vector<int>> {
    void AddEdge(int x , int y) {
        this->at(x).push_back(y) , this->at(y).push_back(x);
    }
};
void Del(vector<int> &vec , int element) {
    for(auto it = vec.begin() ; it != vec.end() ; ++it) {
        while(*it == element) {
            it = vec.erase(it);
            if(it == vec.end()) return ;
        }
    }
}
Tree getroot(Tree x , int rt) {
    queue<int> que;
    que.push(rt);
    while(que.size()) {
        int cur = que.front();
        que.pop();
        for(auto nxt : x[cur]) {
            Del(x[nxt] , cur);
            que.push(nxt);
        }
    }
    return x;
}

int Log2[1 << M];
struct TreeMatcher {

vector<int> dp[N][M];
int dfs(Tree &S , Tree &T , int s , int t) {
    vector<int> &cur = dp[s][t];
    if(!cur.empty()) return cur.back();
    cur.resize(1 << T[t].size());
    cur[0] = 1;
    for(auto nxt : S[s]) {
        for(int i = (int)cur.size() - 1 ; ~i ; --i)
            for(int j = i ; j ; j ^= (j & -j)) {
                int node = Log2[j & -j];
                if(cur[i ^ (1 << node)])
                    add(cur[i] , 1LL * cur[i ^ (1 << node)] * dfs(S , T , nxt , T[t][node]) % mod);
            }
    }
    return cur.back();
}
int match(Tree &S , Tree &T) {
    if(S.size() < T.size())
        return 0;
    if(T.size() <= 1)
        return S.size();

    auto clr = [&] {
        for(int i = 0 ; i < S.size() ; ++i)
            for(int j = 0 ; j < T.size() ; ++j) dp[i][j].clear();
    };
    int ans = 0;
    Tree s = getroot(S , 0);
    for(int j = 0 ; j < T.size() ; ++j) {
        Tree t = getroot(T , j);
        clr();
        for(int i = 0 ; i < S.size() ; ++i)
            add(ans , dfs(s , t , i , j));
    }
    return ans;
}

};

inline int Inv(int x) {
    return x <= 1 ? x : 1LL * (mod - mod / x) * Inv(mod % x) % mod;
}

Tree S , T;
TreeMatcher matcher;

int main() {
    auto Input = [&](Tree &tree) {
        int n ;
        scanf("%d" , &n);
        tree.resize(n);

        for(int i = 1 , x , y ; i < n ; ++i) {
            scanf("%d %d" , &x , &y);
            tree.AddEdge(x - 1, y - 1);
        }
    };
    Input(S) , Input(T);
    *Log2 = -1 ; for(int i = 1 ; i < (1 << M) ; ++i) Log2[i] = Log2[i >> 1] + 1;
    printf("%lld\n" , 1LL * matcher.match(S , T) * Inv(matcher.match(T , T)) % mod);
    return 0;
}