ABC-F - Tree and Constraints

Description

对于一棵 n 个节点的树，每个边染成黑色或白色。给出 m 条限制；每个限制 (u,v) 要求从 u 到 v 的路径至少有一条黑边，求同时满足所有限制的染色总方案数。

Solution

设第 i 个限制为 A_i，则答案为：

\Big|\bigcap_{i=1}^nA_i\Big|

这并不好求，但都能转化到这个形式了，丰富的经验告诉我们这是一道容斥题。

转化：

U-\Big|\bigcup_{i=1}^n \overline{A_i}\Big|

后半段式子根据容斥公式转化为：

\Big|\bigcup_{i=1}^n \overline{A_i}\Big|=\sum\limits_{T\subset U}(-1)^{|T|+1}\Big|\bigcap_{j=1}^{|T|}\overline{A_{T_j}}\Big|

为了使问题更直观，将限制条件状态压缩，若第 i 个不满足，则 S_i=1，否则为 0。

设 f(S) 为状态 S 的方案数，则：

\Big|\bigcup_{i=1}^n \overline{A_i}\Big|=\sum\limits_{T\subset U}(-1)^{|T|+1}f(T)

于是我们求出所有 f(S) 的值套入这个公式即可。

现在思考如何求每个 f(S)。

发现 f(S) 代表属于 S 的限制条件的路径上，边的颜色全为白色，其它边放飞自我的方案数。

则我们只需要直到多少边必须是白色即可，这相当于求出这些路径的并集有多少边。

发现 N\le50，所以所有的边我们同样可以状压起来。

设 path_x 表示从根节点到 x 经过的边的状压数值；

设 info_{x,y} 表示 x 和 y 的路径上的边的状压数值。

则根据经典的树上异或性质： info_{x,y}=path_x \oplus path_y。

求出 S 的所有限制条件的 info 的并集，即为 S 已经确定的白边个数；

设这个数为 cnt，则 f(S)=2^{n-1-cnt}。

最终答案为 2^{n-1}-\sum\limits_{S=1}^{2^m-1} f(S)。

注意细节！！！

• 64位使用 __builtin_popcountll。
• 枚举状压时，S\in[1,2^m-1]，之所以不从 0 开始，是因为 0 的状态是全集，而我们枚举时要算的是非法答案。

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define int long long
using namespace std;
const int N = 51,M = 21;
int n,m,path[N],info[M];
struct EDGE{int to,nxt;}e[N<<1];
int h[N],qcnt;
void adedge(int x,int y){e[++qcnt] = (EDGE){y,h[x]},h[x]=qcnt;}
void dfs(int x,int fa)
{
    for(int i=h[x];i;i=e[i].nxt)
    {
        int v = e[i].to;
        if(v==fa) continue;
        path[v] = path[x] | (1ll<<v);
        dfs(v,x);
    }
}
// 64 位使用 __builtin_popcountll() !!! 
int f(int S)
{
    int edge=0ll,num = __builtin_popcountll(S);
    rep(i,0,m-1) if(S&(1ll<<i)) 
        edge |= info[i+1];
    return (1ll<<(n - 1 - __builtin_popcountll(edge)))*(num&1 ? 1ll : -1ll);
} 
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    rep(i,1,n-1) {
        int x,y; cin>>x>>y;
        adedge(x,y),adedge(y,x);
    }
    dfs(1,0);
    cin>>m;
    int U = (1ll<<m)-1;
    rep(i,1,m) 
    {
        int x,y; cin>>x>>y;
        info[i] = path[x]^path[y];
    }
    int ans=0ll;
    rep(S,1,U) // S = 0 的情况就是全集本身 
    {
        ans += f(S);
    }
    int uans = (1ll<<(n-1));
    cout<<uans-ans;
    return 0;
}