题意

给你若干限制,限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边,数一下以一为根的满足限制的树的个数。
$n \leq 13$,限制总数 $\leq 100$

题解

这个题目太神仙了。。远古 CF 场的题目还是好。
考虑设 $f_{v,S}$ 表示 $v$ 节点子树内的点是 $S$ 的树的个数。答案是 $f_{0,U}$ (将点的标号减一后)
首先我们考虑一下不考虑限制怎么转移:一个 naive 的想法是:
$$f_{v,S} = \sum_{T \subseteq S} \sum_{x \in T} f_{x,T}* f_{v,S-T}$$
也就是枚举这次将那些点拿下去建一个子树。
但是我们考虑到会重复:我们考虑子树内的点集 $\{1,2,3,4,5\}$ 如果这样统计,那么方案 $\{1,2\} \{3,4,5\}$ 和 $\{3,4,5\} \{1,2\}$ 都会被计入,但是显然这两种方案是应该被计入一次的。
于是我们考虑固定 $T$ 内的一个点,这样就不会出现上面的情况了。
接下来我们来考虑限制,我们其实只需要转移的时候排除掉所有不正确的情况就好了:
1. lca(u,v) = c
- 考虑如果你现在枚举的这个点为 $c$ 但是 $u,v$ 都在一个子树中,这显然不行。
- 考虑如果 $c$ 在你枚举的这个子树,那么 $u,v$ 也必须在这个子树中
2. $u,v$ 有一条边
- 如果这个边的一个端点在你现在枚举的点上,那么另一端点只能有至多一个点在这个子树中,并且如果这个点在子树中,需要强制这个点为子树的根。
- 如果端点不在你枚举的点上,$u,v$ 只能同属于这个子树或同不属于这个子树。

然后分类讨论一下就做完了

/*
 * Author: RainAir
 * Time: 2019-10-08 19:07:45
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 13+2;
const int MAXM = 1000+5;
#define int LL
int f[MAXN][(1<<MAXN)+3];
int n,m,q;
int pc[(1<<MAXN)+3];
int a[MAXM],b[MAXM],c[MAXM];
int G[MAXN][MAXN];
struct Edge{
    int u,v;
    Edge(int u=0,int v=0) : u(u),v(v) {}
}e[MAXN];
bool in(int x, int s){ return s & (1 << x); }
inline int dfs(int v,int S){
    int &ans = f[v][S];
    if(pc[S] == 1) return ans = (S == (1<<v));
    if(ans != -1) return ans;
    ans = 0;S ^= (1<<v);
//    int TT = ((1<<n)-1)^(1<<0);
    int son = 0;
    FOR(i,0,n-1) if((1<<i)&S) son = i; // 固定连通块包含的点,避免重复(不包含这个点的连通块总会在枚举的集合的补集被取到)
    for(int T = S;T;T = (T-1)&S){
        if(!((1<<son)&T)) continue;
        // lca
        // 如果 lca 在这个点上,那么两个点要在不同的子树里
        // 如果 lca 在子树,那么这两个点都要在子树里
        bool flag = true;
        FOR(i,1,q){
            if(c[i] == v && (T&(1<<a[i])) && (T&(1<<b[i]))){
                flag = 0;
                break;
            }
        }
        if(!flag) continue;
        FOR(i,1,q){
            if(T&(1<<c[i]) && !((T&(1<<a[i])) && (T&(1<<b[i])))){
                flag = 0;
                break;
            }
        }
        if(!flag) continue;
        // edge
        // 如果端点在这个点上,那么另一个点只能有一个在这个子树里
        // 如果端点不在这个点上,不能一个在子树一个不在子树
        FOR(i,1,m){
            if(e[i].u != v && e[i].v != v && ((bool)(T&(1<<e[i].u))) ^ ((bool)(T&(1<<e[i].v)))){
                flag = 0;
                break;
            }
        }
        if(!flag) continue;        
        int cnt = 0,x = 0;
        FOR(i,1,m){
            if(e[i].u == v || e[i].v == v){
                int t = e[i].u == v ? e[i].v : e[i].u;
                if(T&(1<<t)) cnt++,x = t;
                if(cnt > 1){
                    flag = 0;
                    break;
                }
            }
        }
        if(!flag) continue;
//            if(v == 1 && S == 4) DEBUG(T),DEBUG(cnt),DEBUG(x);
        if(cnt == 1) ans += dfs(x,T)*dfs(v,(S^T)^(1<<v));
        else{
            FOR(x,0,n-1){
                if(T&(1<<x))
                    ans += dfs(x,T)*dfs(v,(S^T)^(1<<v));
                  //  if(v == 0 && T == 6) DEBUG(dfs(x,T)),DEBUG(x);
            }
        }
    }
    return ans;
}

signed main(){
    scanf("%lld%lld%lld",&n,&m,&q);CLR(f,-1);
    FOR(i,1,(1<<n)-1) pc[i] = pc[i>>1]+(i&1);
    FOR(i,1,m){
        int u,v;scanf("%lld%lld",&u,&v);--u;--v;
        G[u][v] = G[v][u] = 1;
        e[i] = Edge(u,v);
    }
    FOR(i,1,q) scanf("%lld%lld%lld",a+i,b+i,c+i),--a[i],--b[i],--c[i];
    FOR(i,0,n-1) f[i][(1<<i)] = 1;
    printf("%lld\n",dfs(0,(1<<n)-1));
    return 0;
}

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/862/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏