【bzoj4455】[Zjoi2016]小星星

Problem

Description

小Y是一個心靈手巧的女孩子，她喜歡手工制作一些小飾品。她有n顆小星星，用m條彩色的細線串了起來，每條細線連着兩顆小星星。有一天她發現，她的飾品被破壞了，很多細線都被拆掉了。這個飾品隻剩下了n-1條細線，但通過這些細線，這顆小星星還是被串在一起，也就是這些小星星通過這些細線形成了樹。

小Y找到了這個飾品的設計圖紙，她想知道現在飾品中的小星星對應着原來圖紙上的哪些小星星。如果現在飾品中兩顆小星星有細線相連，那麼要求對應的小星星原來的圖紙上也有細線相連。

小Y想知道有多少種可能的對應方式。隻有你告訴了她正确的答案，她才會把小飾品做為禮物送給你呢。

Input

第一行包含個2正整數n,m，表示原來的飾品中小星星的個數和細線的條數。

接下來m行，每行包含2個正整數u,v，表示原來的飾品中小星星u和v通過細線連了起來。

這裡的小星星從1開始标号。保證u≠v，且每對小星星之間最多隻有一條細線相連。

接下來n-1行，每行包含個2正整數u,v，表示現在的飾品中小星星u和v通過細線連了起來。

保證這些小星星通過細線可以串在一起。

Output

輸出共1行，包含一個整數表示可能的對應方式的數量。如果不存在可行的對應方式則輸出0。

Sample Input

4 3

1 2

1 3

1 4

4 1

4 2

4 3

Sample Output

6

資料範圍

對于100%的資料 n<=1000

Solution

首先，這道題有很多的部分分。

20%可以暴力枚舉。

40%可以當做一條鍊的情況做狀壓DP。

總共60%~70%的資料不用卡常。

當然剩下的30%我就呵呵哒。

咳咳，進入正題。

首先我們考慮一種比較直覺的狀壓方法，用 f[i][state] 表示i号點所在的子樹，使用了state所表示的點進行映射。這樣每一次轉移都需要枚舉子集，複雜度 O(3n∗n2) ，需要非常高（jiao）深（shi）的常數優化技巧。

這種做法的複雜度瓶頸明顯出現在枚舉子集上，那怎麼優化這個枚舉子集的過程呢？我們考慮使用容斥原理。假設每個點映射的點構成的集合是可重集（用 state 表示），也就是說樹上兩個不同點的映射可以相同。那麼首先枚舉 state ，複雜度 O(2n) ，接下來隻需要記 f[i][j] 表示第樹上i号點映射圖中j号點的方案數，枚舉所有孩子的 f[k][l] ，就可以做到 O(n3) 計算。注意k的枚舉一共隻有n次。

接下來使用容斥原理，對于 State=Si ，我們記 reti=Σf[root][j],j∈Si ，若 |Si|≡n(mod2) ，則 ans+=reti ，否則 ans−=reti 。隻是使用了同加異減的想法，非常簡單。

至此，整個問題在 O(2n∗n3) 的時間内得到完成，隻需要少量的常數優化即可通過本題。

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define red(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

inline int read() {
    char c = getchar(); int x = , f = ;
    while(!isdigit(c)) { if (c == '-') f = -; c = getchar(); }
    while(isdigit(c)) { x = x *  + c - '0'; c = getchar(); }
    return x * f;
}

const int N = ;
int n, m, tail = ;
ll f[N][N];
int hash[N], g[N][N], gt[N][N], fa[N], p[N], q[N], head[N], e[N][];

void addedge(int s, int t) { e[++tail][] = t; e[tail][] = head[s]; head[s] = tail; }
void bfs(int s) {
    int l = , r = ; q[] = s;
    while(l <= r) {
        int x = q[l], ch = ; l++;
        rep(i, , n) if (gt[x][i] && i != fa[x]) q[++r] = i, fa[i] = x, ++ch, addedge(x, i);
        if (ch == ) hash[x] = ;
    }
}
void dp(int s, int state, int cnt) {
    red(i, n, ) {
        int x = q[i];
        if (hash[x]) continue;
        rep(j, , cnt) {
            for(int i = head[x]; i != -; i = e[i][]) {
                int ch = e[i][]; ll num = ;
                if (fa[ch] != x) continue;
                rep(k, , cnt) if (g[p[j]][p[k]]) num += f[ch][k];
                f[x][j] *= num;
            }
        }
    }
}
int get_cnt(int x) {
    int cnt = , j = ;
    while(x) {
        j++;
        if (x & ) p[++cnt] = j;
        x >>= ;
    }
    return cnt;
}
int main() {
    n = read(); m = read();
    rep(i, , n) g[i][i] = ;
    int x, y;
    rep(i, , m) x = read(), y = read(), g[x][y] = g[y][x] = ;
    rep(i, , n - ) x = read(), y = read(), gt[x][y] = gt[y][x] = ;
    memset(hash, , sizeof(hash));
    fa[] = ;
    rep(i, , n) head[i] = -;
    bfs();
    ll ans = , tag = n % ;
    rep(state, , (( << n) - )) {
        int cnt = get_cnt(state);
        ll flag = (cnt %  == tag) ?  : -, _ans = ;
        rep(i, , n) rep(j, , cnt) f[i][j] = ;
        dp(, state, cnt);
        rep(i, , cnt) _ans += f[][i];
        ans += flag * _ans;
    }
    cout << ans << endl;
    return ;
}
           

尾聲

聽說寫ZJOI的題解會有很多人看诶

然而我馬上也要省選啦TAT

咕咕

加油啦

End.