AT_ddcc2017_final_d なめらかな木 题解

· · 题解

首先考虑暴力 DP，设 f(i,v_1,v_2,now) 为已经将前 i 个数填入，i 填在 v_1，j 填在 v_2 点，已经填完点的状态是 now（状压一下存在一个 long long 里）的方案数。转移时直接枚举下一个点暴力转移，只需要保证新的点没有被访问过，并且填上新点后，v_1 的所有邻接点都被填上即可。

其实直接暴力转移，复杂度是对的。

我们考虑对于一个状态 (i,v_1,v_2,now)，将 v_1 和 v_2 在树中剪掉，剩下的连通块（最多 7 个，因为每个点度数最多为 4）中，要么全被填了，要么都没被填。因为一个连通块内被填的点上的数一定小于等于 n-2，后面填的点一定和这些点的差一定大于 2，因此一定不合法。

状态数最多为 n^3 \times 2^7，复杂度 O(n^3 \times 2^7)。

注意特判 n=1 的情况。

代码


#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
    char ch=getchar();
    T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x*=f;rd(args...);
}
const int mod=1e9+7;
unordered_map<long long,int> mp[65][65][65];
vector<int> e[65];int n;
signed main(){
    rd(n);
    if(n==1){
        printf("1\n");
        return 0;
    }
    for(int i=1;i<n;i++){
        int x,y;rd(x,y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int v1=1;v1<=n;v1++)
        for(int v2=1;v2<=n;v2++){
            if(v1==v2)continue;
            mp[2][v1][v2][(1ll<<v2)|(1ll<<v1)]+=1;
        }
    for(int i=2;i<n;i++){
        for(int v1=1;v1<=n;v1++){
            for(int v2=1;v2<=n;v2++){
                if(v1==v2)continue;
                long long bas=0;
                for(int x:e[v1])bas|=(1ll<<x);
                for(int x=1;x<=n;x++){
                    for(pair<long long,int> p:mp[i][v1][v2]){
                        if(p.first&(1ll<<x))continue;
                        if(((p.first|(1ll<<x))&bas)==bas){
                            (mp[i+1][v2][x][p.first|(1ll<<x)]+=mp[i][v1][v2][p.first])%=mod;
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for(int v1=1;v1<=n;v1++)
        for(int v2=1;v2<=n;v2++){
            if(v1==v2)continue;
            for(auto p:mp[n-1][v1][v2])
                (ans+=p.second)%=mod;
        }
    printf("%d\n",ans);
    return 0;
}