七海ノ心象素描

所有的为时已晚都是恰逢其时

Nanami^2 avatar

Author

Nanami^2

大一学生 | 不是很聪明的样子

Twitter GitHub
Telegram

我的频道

不定期推送灵感笔记

t.me/kisanami_blog
联系方式
QQ 群
1072614878
发送邮件

「NOIP Record」#1 树形DP（1）

一切的开始

Nanami^2
Nanami^2 Even in the rain.
2023年05月04日
预计阅读 27 分钟
6172 字

树形 DP 计数。

luogu8867 建造军营

对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。

然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 fxf_x 为军营只在以 xx 为根的子树中出现，且至少存在 11 个军营的方案数。

转移时对于边 (x,y)(x,y)，如果 yy 中没有军营，那么子树 yy 中每条边以及 (x,y)(x,y) 看守与否均可，方案数 2szy2^{sz_y}；否则 (x,y)(x,y) 一定要看守，方案数 fyf_y。

还要乘上 xx 所在边双中任意选择的方案数，并且减掉子树中一个都不选的方案。

fx=2cx∏y∈son(x)(fy+2szy)−2szx−1f_x = 2^{c_x} \prod_{y \in son(x)} (f_y+2^{sz_y}) - 2^{sz_x-1}

但这样求出的并不是答案。

直接对一个 fxf_x 求对答案的贡献会产生重复，举个例子，如果 xx 只有 yy 这一个儿子，那么 yy 节点上建造了军营，xx 没有建造，那么这样的情况就会在 fxf_x 与 fyf_y 中被重复统计到。

考虑将节点贡献在 LCA⁡\operatorname{LCA} 处统计。在节点 xx 处的贡献，要么是 xx 节点中建造了，要么是 xx 有至少两个儿子所在子树中建造了。这两种情况都在 fxf_x 中被统计过。

非法方案是 xx 没有建造军营，并且只有一个儿子 yy 所在子树中建造了，容易得到这部分就是

2dcc−1−(szx−1)∑y∈son(x)fy×2szx−szy−12^{dcc-1-(sz_x-1)}\sum_{y \in son(x)} f_y \times 2^{sz_x-sz_y-1}

最后乘上每条非树边可选可不选的方案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=5e5+5, M=1e6+5, mod=1e9+7;
int n, m, num, cnt, pw[M];
int ans, bel[N], c[N], sz[N], f[N];




struct Gr {
    int tot, h[N], to[M<<1], nxt[M<<1];
    void add(int x,int y) { to[++tot]=y, nxt[tot]=h[x], h[x]=tot; }
} G, T;


int dcc, tp, dfn[N], low[N], st[N];
void tarjan(int x,int lst) {
    dfn[x]=low[x]=++num;
    st[++tp]=x;
    for(int i=G.h[x];i;i=G.nxt[i]) {
        int y=G.to[i];
        if(i!=(lst^1)) {
            if(!dfn[y]) {
                tarjan(y,i);
                low[x]=min(low[x],low[y]);
            } else low[x]=min(low[x],dfn[y]);
        }
    }
    if(dfn[x]==low[x]) {
        int y=0; ++dcc;
        do y=st[tp--], ++c[dcc], bel[y]=dcc; while(x!=y);
    }
}
void dfs(int x,int fa) {
    sz[x]=1, f[x]=pw[c[x]];
    for(int i=T.h[x];i;i=T.nxt[i]) {
        int y=T.to[i];
        if(y==fa) continue;
        dfs(y,x);
        (f[x]*=(f[y]+pw[sz[y]])%mod)%=mod;
        sz[x]+=sz[y];
    }
    (f[x]-=pw[sz[x]-1]-mod)%=mod;
    int F=f[x];
    for(int i=T.h[x];i;i=T.nxt[i]) {
        int y=T.to[i];
        if(y==fa) continue;
        (F-=f[y]*pw[sz[x]-sz[y]-1]-mod)%=mod;
    }
    (ans+=F*pw[dcc-sz[x]]%mod)%=mod;
}
void suodian() {
    rep(x,1,n) {
        for(int i=G.h[x];i;i=G.nxt[i]) {
            int y=G.to[i];
            if(bel[x]!=bel[y]) {
                T.add(bel[x],bel[y]);
            } else ++cnt;
        }
    }
}
signed main() {
    G.tot=1;
    n=read(), m=read();
    rep(i,1,m) {
        int x=read(), y=read();
        G.add(x,y), G.add(y,x);
    }
    tarjan(1,0);
    suodian();
    pw[0]=1;
    for(int i=1;i<=max(n,m);++i) pw[i]=pw[i-1]*2%mod;
    dfs(1,0);
    printf("%lld\n",ans*pw[cnt>>1]%mod);
}

自己顺着错误的想法推导的过程中，也得到了很多教训。

  • 计数的式子，一定再三考虑后再写下
  • 不要老是想着容斥掉某些东西
  • 对于边双内部的点、边这类“可以提到外面”的东西，尽量不要放到 DP 的过程里面，太容易写错了，而且会让过程复杂化。
  • 把板子打熟练

luogu7727 风暴之眼（Eye of the Storm）

对于此类有着复杂定义的题目，不妨先静下心来进行一些观察。

  • 首先如果一个节点是初始为 00 的 AND\text{AND} 型节点或者初始值为 11 的 OR\text{OR} 型节点，那么一定不会改变自身的颜色。称其为黑点，其他成为白点。

  • 白点最多变化一次。

  • 同一个初始权值白色连通块内，要么权值都变化一次，要么都不变。证明略。

  • 那么一个白色连通块何时才不会改变权值呢？只需要考虑它周围的一圈黑点。如果是 (0,AND)(0,\text{AND}) 与 (0,OR)(0,\text{OR})，(1,OR)(1,\text{OR}) 与 (1,AND)(1,\text{AND})，那么右边就不会因为左边改变权值，而两个不同类型的白点 (1,AND)(1,\text{AND}) 与 (0,OR)(0,\text{OR}) 或者一黑一白是会影响对方的。因此推出一个白色连通块的权值不改变，当且仅当整个连通块以及周围的一圈黑点，权值都相同。

  • 如何让一个白色连通块达到权值相同？需要满足以下两个条件之一。1. 连通块内存在一个白点，满足初始权值等于最终权值。2. 周围存在一个黑点，满足其与这个连通块的最终权值相同。

考虑用树形 DP 来做。

为了方便采用如下标记

  • p(0/1)p(0/1)，黑点还是白点。
  • q(0/1)q(0/1)，初始权值是否等于最终权值。
  • r(0/1)r(0/1)，此时这个连通块内能否满足最终权值的条件。

每一种状态都存在吗？不然。

首先 qq 和 rr 就存在非法组合。

对于黑点，能接上它的白色连通块一定都满足最终权值的条件，且其初始权值必然等于最终权值。

对于白点，如果其初始权值等于最终权值，那么接上一个合法的白色连通块之后，必然满足最终权值条件。

因此随便钦定一个点为根，然后设 fx,0/1/2/3f_{x,0/1/2/3} 为在以 xx 为根的子树中

  • p(0),q(0),r(0)p(0),q(0),r(0)
  • p(1),q(0),r(0)p(1),q(0),r(0)
  • p(1),q(1),r(0)p(1),q(1),r(0)
  • p(1),q(1),r(1)p(1),q(1),r(1)

然后考虑转移，用上上面的结论。方式是将 xx 的子节点 yy 看作是一个连通块，按照把 yy 接到 xx 上形成新的连通块来计数，同时根据 axa_x 与 aya_y 得到对应的转移方案。

开个临时数组 gg。

对于 xx 和 y∈son(x)y \in son(x)，如果 ax=aya_x = a_y

g0=fx,0⋅(fy,0+fy,1)g_0 = f_{x,0} \cdot (f_{y,0} + f_{y,1}) g1=fx,1⋅(fy,0+fy,1+fy,2+fy,3)g_1 = f_{x,1} \cdot (f_{y,0} + f_{y,1} + f_{y,2} + f_{y,3}) g2=fx,2⋅(fy,1+fy,2+fy,3)+fx,3⋅(fy,1+fy,2)g_2 = f_{x,2} \cdot (f_{y,1}+f_{y,2}+f_{y,3}) + f_{x,3} \cdot (f_{y,1}+f_{y,2}) g3=fx,3⋅fy,3g_3 = f_{x,3} \cdot f_{y,3}

若 ax≠aya_x \neq a_y

g0=0g_0 = 0 g1=fx,1⋅(fy,1+fy,2)g_1 = f_{x,1} \cdot (f_{y,1} + f_{y,2}) g2=fx,2⋅(fy,1+fy,2+fy,3)+fx,3⋅(fy,2+fy,3)g_2 = f_{x,2} \cdot (f_{y,1}+f_{y,2} + f_{y,3}) + f_{x,3} \cdot (f_{y,2} + f_{y,3}) g3=fx,3⋅fy,1g_3 = f_{x,3} \cdot f_{y,1}

然后

fx←gf_x \leftarrow g

答案是 f1,0+f1,1+f1,2f_{1,0}+f_{1,1}+f_{1,2}

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=2e5+5, mod=998244353;
int n, a[N], f[N][4], g[4];
int tot, h[N], to[N<<1], nxt[N<<1];
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void dp(int x,int fa) {
    f[x][0]=f[x][1]=f[x][3]=1;
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dp(y,x);
        SET(g,0);
        if(a[x]==a[y]) {
            g[0]=f[x][0]*(f[y][0]+f[y][1])%mod;
            g[1]=f[x][1]*((f[y][0]+f[y][1])%mod+(f[y][2]+f[y][3])%mod)%mod;
            g[2]=(f[x][2]*(f[y][1]+f[y][2]+f[y][3])%mod+f[x][3]*(f[y][1]+f[y][2])%mod)%mod;
            g[3]=f[x][3]*f[y][3]%mod;
        } else {
            g[0]=0;
            g[1]=f[x][1]*(f[y][1]+f[y][2])%mod;
            g[2]=(f[x][2]*(f[y][1]+f[y][2]+f[y][3])%mod+f[x][3]*(f[y][2]+f[y][3])%mod)%mod;
            g[3]=f[x][3]*f[y][1]%mod;
        }
        memcpy(f[x],g,sizeof(g));
    }
}
signed main() {
    n=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n-1) {
        int x=read(), y=read();
        add(x,y), add(y,x);
    }
    dp(1,0);
    printf("%lld\n",(f[1][0]+f[1][1]+f[1][2])%mod);
}
  • 状态间的转移应仔细推敲。
  • 见到这种看起来很吓人的题目，千万不要手足无措白白浪费时间，尝试观察性质，哪怕打个暴力呢。

luogu8973 『GROI-R1』 继续深潜，为了同一个梦想

一个点被这样的点集所包含，只有两种情况。

要么是从子树内到某个祖先的一条链，要么是端点在两个子节点的子树内，跨越这个点的一条链。

考虑一个转化，求 ansians_i 时，将 ii 钦定为根。那么前者转化为子树内到达 ii 的链。

设 fr(x)f_r(x) 为整棵树以 rr 为根，在以 xx 为根的子树内，有多少以 xx 为端点且满足条件的的链，其实就是在子树内除了 xx 选择至少一个节点的方案数。

fr(x)=∑y∈son(x)(2fr(y)+1)f_{r}(x) = \sum_{y \in son(x)} (2f_r(y) +1)

然后考虑第二种情况，其实就是两条上述的链拼凑而成，

设 S=fr(x)S = f_r(x)，F(x)=2fr(x)+1F(x) = 2f_r(x)+1。

对于一个子节点 yy，其贡献为 F(y)⋅(S−F(y)+1)F(y) \cdot (S-F(y)+1)，+1+1 是顺便把第一种情况算上。同时为了避免重复计数，计算完 yy 之后令 S←S−F(y)S \leftarrow S-F(y)。

综上，得到以 rr 为整棵树的根时，以 xx 为根的子树内的答案 gr(x)g_r(x)。

那么如何得到所有结点的答案呢？考虑换根。

发现对于 (x,y)(x,y)，有

fy(x)=fx(x)−F(y)f_y(x) = f_x(x) - F(y) fy(y)=fx(y)+F(x)f_y(y) = f_x(y) + F(x)

直接求即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=5e5+5, mod=1e9+7;
int n, f[N], g[N];
int tot, h[N], to[N<<1], nxt[N<<1];
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
int F(int x) { return (2*f[x]%mod+1)%mod; }
void dfs(int x,int fa) {
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dfs(y,x);
        (f[x]+=2*f[y]+1)%=mod;
    }
}
void dfs2(int x,int fa) {
    int S=0;
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        (S+=F(y))%=mod;
    }
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        (g[x]+=F(y)*(S-F(y)+1+mod)%mod)%=mod;
        (S-=F(y)-mod)%=mod;
    }
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        int tx=f[x], ty=f[y];
        (f[x]-=2*f[y]%mod+1-mod)%=mod;
        (f[y]+=2*f[x]%mod+1)%=mod;
        dfs2(y,x);
        f[x]=tx, f[y]=ty;
    }
}
signed main() {
    n=read();
    rep(i,1,n-1) {
        int x=read(), y=read();
        add(x,y), add(y,x);
    }
    dfs(1,0);
    dfs2(1,0);
    int ans=0;
    rep(i,1,n) ans^=g[i]*i;
    printf("%lld\n",ans);
}

luogu8280 「MCOI-08」Photoelectric Effect

思路并不难想。考虑以 xx 为根的子树和其若干子节点 {yi}\{y_i\}。

设 xx 颜色为 cxc_x，对于 y1y_1 和 y2y_2，以 y1y_1 为根的子树中任何一个节点与 y2y_2 子树中的任意一个节点颜色之并等于 cxc_x。那么两棵子树的颜色集合两两之并都是 cxc_x，这个可以预处理，同时也能看出子树颜色集合必须加入状态中。

从样例中能看到这个并运算不满足交换律，因此预处理时要注意如果集合 S1S_1 与 S2S_2 正反两种并不同，那么不合法。

考虑到颜色关系的特殊性，需要一棵一棵地加入子树来统计答案。特别的，第一棵子树不存在颜色限制。

为了避免包含等不必要的麻烦，设 SxS_x 为以 xx 为根的子树中，不含 xx 的颜色集合。同时设 S1⊗S2S_1 \otimes S_2 表示 S1S_1 中任意元素并上 S2S_2 中任意元素结果为同一种颜色，且满足 S1⊗S2=S1⊗S1S_1 \otimes S_2 = S_1 \otimes S_1。

设 fx,i,Sf_{x,i,S} 为以 xx 为根的子树，xx 的颜色是 ii，其他子树内的颜色集合是 SS 的方案数。

考虑 fy,j,S0f_{y,j,S_0} 如何转移。

条件是 T=S0∪{j}T=S_0 \cup \{j\}，存在 SS 满足 S⊗T=iS \otimes T = i，贡献为

fy,j,S0⋅fx,i,S→fx,i,S∣T′f_{y,j,S_0} \cdot f_{x,i,S} \rightarrow f'_{x,i,S|T}

特别地，对于 xx 的第一棵子树

fy,j,S0→fx,i,S0∪{j}f_{y,j,S_0} \rightarrow f_{x,i,S_0 \cup \{j\}}

复杂度 O(nk22k)O(nk2^{2k})

相当恐怖，不过剪掉无用状态后就跑不满，可过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=1e5+5, mod=1e9+7;
int T, n, k, U, son[N], t[5][5], p[32][32], f[N][5][32], g[5][32];
int tot, h[N], to[N<<1], nxt[N<<1];
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
int get(int x,int y) {
    int res=-2;
    rep(i,0,k-1) if(x&(1<<i)) {
        rep(j,0,k-1) if(y&(1<<j)) {
            if(res==-2) res=t[i][j];
            else if(res!=t[i][j]) res=-1;
        }
    }
    swap(x,y);
    rep(i,0,k-1) if(x&(1<<i)) {
        rep(j,0,k-1) if(y&(1<<j)) {
            if(res==-2) res=t[i][j];
            else if(res!=t[i][j]) res=-1;
        }
    }
    return res;
}
void dp(int x,int fa) {
    if(!son[x]) {
        rep(i,0,k-1) f[x][i][0]=1;
        return;
    }
    int fg=0;
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dp(y,x);
        if(!fg) {
            rep(nw,0,k-1) rep(S,0,U) rep(w,0,k-1) {
                (f[x][nw][S|(1<<w)]+=f[y][w][S])%=mod;
            }
            fg=1;
            continue;
        }
        rep(nw,0,k-1) rep(S,1,U) g[nw][S]=0;
        rep(nw,0,k-1) rep(S0,0,U) if(f[y][nw][S0]) rep(S,1,U) {
            int T=S0|(1<<nw);
            if(p[S][T]==-1) continue;
            (g[p[S][T]][S|T]+=f[x][p[S][T]][S]*f[y][nw][S0]%mod)%=mod;
        }
        memcpy(f[x],g,sizeof(g));
    }
}
void solve() {
    n=read(), k=read();
    U=(1<<k)-1;
    tot=0;
    rep(i,1,n) {
        h[i]=son[i]=0;
        SET(f[i],0);
    }
    SET(p,-1);
    rep(i,0,k-1) rep(j,0,k-1) {
        int x=read()-1;
        t[i][j]=x;
    }
    rep(i,2,n) {
        int x=read();
        ++son[x];
        add(x,i), add(i,x);
    }
    rep(i,1,U) rep(j,1,U) p[i][j]=get(i,j);
    dp(1,0);
    int ans=0;
    rep(i,0,k-1) rep(j,0,U) (ans+=f[1][i][j])%=mod;
    printf("%lld\n",ans);
}
signed main() {
    T=read();
    while(T--) solve();
}
  • 状态压缩，优先使用刷表法
  • 考虑再三后再预处理
  • 预处理时一定不要把初始状态设成无解状态
  • 加入子树的计数思路
  • 一开始竟然设 SxS_x 为以 xx 为根的子树的所有颜色，导致很多麻烦且干扰思路与转移。

最后附上我一开始写的 SB 预处理。

之前也在预处理上吃过亏啊，以后要多加小心。

void init() {
    rep(i,1,U) rep(j,1,U) if(p[i][j]<0) {
        int kk=-1;
        // 从头开始就错了
        rep(k1,0,4) if(i&(1<<k1)) {
            int q=-1;
            rep(k2,0,4) if(j&(1<<k2)) {
                if(q==-1) q=p[k1][k2];
                else if(q!=p[k1][k2]) { kk=-1; goto pq; }
            }
            if(kk==-1) kk=q;
            else if(kk!=q) { kk=-1; break; }
        }
        pq: p[i][j]=kk;
    }
    rep(i,1,U) rep(j,1,U) if(p[i][j]!=p[j][i]) p[i][j]=p[j][i]=-1;
}

luogu3349 [ZJOI2016]小星星

题意比较裸。

设 fx,i,G0f_{x,i,G_0} 为以 xx 为根的子树，节点 xx 映射到原图中的 ii，此时子树内映射到图中的节点集合为 G0G_0 的方案数。

转移则遇到了困难，首先复杂度就很高了，其次 G0G_0 这一维的转移要把 G0G_0 不重不漏地划分成 xx 的子节点个数个非空子集，也就是一个子集卷积。

考虑困难的来源是「每个节点只能映射一次」这个限制导致了必须记录 G0G_0。不难发现只要有节点映射了超过一次，那么一定有节点没有被映射，这个是可以容斥的。

考虑枚举集合 S′⊆SS' \subseteq S，其中 SS 是节点集合，表示不能映射 S′S' 中的节点，进行最原始的集合间的容斥即可。

考虑此时如何求方案数。设 fx,if_{x,i} 表示以 xx 为根的子树，节点 xx 映射到了图中节点 ii 的方案数，容易写出

fx,i=∏y∈son(x)∑(i,j)∈Gfy,jf_{x,i} = \prod_{y \in son(x)} \sum_{(i,j) \in G} f_{y,j}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=20;
int n, m, U, S, popcnt[1<<17];
int lg[1<<17];
int tot, h[N], to[N*N], nxt[N*N];
int t2, h2[N], to2[N*N], nxt2[N*N];
uint ans, f[N][N];
int lowbit(int x) { return x&-x; }
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void add2(int x,int y) {
    to2[++t2]=y, nxt2[t2]=h2[x], h2[x]=t2;
}
void dp(int x,int fa) {
    for(int i=h2[x];i;i=nxt2[i]) {
        int y=to2[i];
        if(y==fa) continue;
        dp(y,x);
    }
    for(int T=S^U;T;T-=lowbit(T)) {
        int a=lg[lowbit(T)];
        f[x][a]=1;
        for(int i=h2[x];i;i=nxt2[i]) {
            int y=to2[i];
            if(y==fa) continue;
            int dlt=0;
            for(int j=h[a];j;j=nxt[j]) dlt+=f[y][to[j]];
            f[x][a]*=dlt;
        }
    }
}
signed main() {
    n=read(), m=read();
    U=(1<<n)-1;
    rep(i,1,m) {
        int x=read(), y=read();
        add(x,y), add(y,x);
    }
    lg[1]=1;
    rep(i,1,n-1) {
        int x=read(), y=read();
        add2(x,y), add2(y,x);
        lg[1<<i]=i+1;
    }
    for(S=0;S<=U;++S) {
        popcnt[S]=popcnt[S>>1]+(S&1);
        int ss=0;
        rep(i,1,n) rep(j,1,n) f[i][j]=0;
        dp(1,0);
        for(int i=S^U;i;i-=lowbit(i)) ss+=f[1][lg[lowbit(i)]];
        if(popcnt[S]&1) ans-=ss; else ans+=ss;
    }
    printf("%llu\n",ans);
}

 

树形背包。

用来解决树形 DP 中，子树之间会互相影响的转移。具体方法是先依次合并各子树信息，再处理根的影响。

为什么是「类」树形背包？因为此类题目一般没有给出作为背包容积的上界，因此必须用当前子树大小卡好复杂度，否则会退化。

因此，在实现上是需要注意的。

ABC287F Components

给定一棵树 T=(V,E)T=(V,E)，求对于 x=1,2,…,nx=1,2,\ldots,n，所有 VV 的子集与 EE 构成的图中，恰好有 xx 个连通块的方案数。对 998244353998244353 取模。

n≤5000n \le 5000

考虑在各子树的父节点处统计贡献。

设 fx,i,0/1f_{x,i,0/1} 表示以 xx 为根的子树，每个节点可选可不选，恰好存在 ii 个连通块，其中 xx 有没有被选择的方案数。

用类似树形背包的方式转移，好处是可以容易考虑一棵子树对其它子树的影响。

如果 xx 不选择，那么对于子节点 yy，其

选不选都不收影响，因此

如果 xx 选择，那么如果 yy 选择了，就会减少一个连通块

fx,j,1⋅(fy,k,0+fy,k+1,1)→gj+k,1f_{x,j,1} \cdot (f_{y,k,0}+f_{y,k+1,1}) \rightarrow g_{j+k,1}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=5005, mod=998244353;
int n, sz[N], f[N][N][2], g[N][2];
int tot, h[N], to[N<<1], nxt[N<<1];
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void dp(int x,int fa) {
    sz[x]=f[x][0][0]=f[x][1][1]=1;
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dp(y,x);
        SET(g,0);


            for(int j=0;j<=sz[x];++j)  for(int k=0;k<=sz[y];++k) {
                (g[j+k][0]+=f[x][j][0]*((f[y][k][0]+f[y][k][1])%mod)%mod)%=mod;
                (g[j+k][1]+=f[x][j][1]*((f[y][k][0]+f[y][k+1][1])%mod)%mod)%=mod;
        }
        rep(j,0,sz[x]+sz[y]) f[x][j][0]=g[j][0], f[x][j][1]=g[j][1];
        sz[x]+=sz[y];
    }
}
signed main() {
    n=read();
    rep(i,1,n-1) {
        int x=read(), y=read();
        add(x,y), add(y,x);
    }
    dp(1,0);
    rep(i,1,n) printf("%lld\n",(f[1][i][0]+f[1][i][1])%mod);
}

luogu8564 ρars/ey

容易设出状态，fx,if_{x,i} 表示以 xx 为根的子树，还剩下 ii 个节点，所需要的最小代价。

把转移过程分为两部分，一部分从子树处继承没有被删去的节点数量，另一部分从 xx 处删点。

设当前加入了 cntcnt 棵子树，那么在合并子树的过程中，最少剩下 cnt+1cnt+1 个节点，这个下界会不断改变，因此要不断更新相应的信息。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=5005, inf=0x3f3f3f3f3f3f3f3f;
int n, a[N], sz[N], f[N][N], g[N];
int tot, h[N], to[2*N], nxt[2*N];
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void addedge(int x,int y) {
    add(x,y), add(y,x);
}
void dp(int x,int fa) {
    sz[x]=1, f[x][1]=0;
    int cnt=0;
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dp(y,x);
        for(int j=cnt+1;j<=sz[x];++j)
            for(int k=1;k<=sz[y];++k)
                g[j+k]=min(g[j+k],f[x][j]+f[y][k]);
        ++cnt, sz[x]+=sz[y];
        f[x][cnt]=inf;
        for(int j=cnt+1;j<=sz[x];++j) f[x][j]=g[j], g[j]=inf;
    }
    f[x][1]=a[sz[x]];
    for(int k=cnt+1;k<=sz[x];++k) f[x][1]=min(f[x][1],f[x][k]+a[k]);
}
signed main() {
    n=read();
    for(int i=2;i<=n;++i) a[i]=read();
    for(int i=1;i<n;++i) {
        int x=read(), y=read();
        add(x,y), add(y,x);
    }
    SET(g,0x3f);
    dp(1,0);
    printf("%lld\n",f[1][1]);
}

luogu6478 [NOI Online #2 提高组] 游戏

如果出现了平局，那么一定是两个点在以它们的 lcalca 为根的，不同的子树中。

在树形 DP 中合并信息是容易的。

设 fx,if_{x,i} 为以 xx 为根的子树，有 ii 个回合没有平的方案数。

合并完子树的过程中，统计出子树内每种颜色的点的数量，然后只要选择和 xx 颜色相反的就能让非平局回合数量加 11。

但是这样得到的是整棵树中，至少有 ii 个非平局回合的方案数。所以套一个二项式反演即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SET(a,b) memset(a,b,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
    int a=0, f=1; char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
    return a*f;
}
const int N=5005, mod=998244353;
int n, m, a[N], sz[N], c[N][2], F[N], G[N], f[N][N], g[N], fac[N], inv[N];
int tot, h[N], to[N<<1], nxt[N<<1];
char s[N];
void add(int x,int y) {
    to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void dp(int x,int fa) {
    ++c[x][a[x]], f[x][0]=sz[x]=1;
    for(int i=h[x];i;i=nxt[i]) {
        int y=to[i];
        if(y==fa) continue;
        dp(y,x);
        for(int j=0;j<=sz[x]+sz[y];++j) g[j]=0;
        for(int j=0;j<=sz[x];++j)
            for(int k=0;k<=sz[y];++k) (g[j+k]+=f[x][j]*f[y][k]%mod)%=mod;
        sz[x]+=sz[y];
        for(int j=0;j<=sz[x];++j) f[x][j]=g[j];
        c[x][0]+=c[y][0], c[x][1]+=c[y][1];
    }
    for(int i=c[x][a[x]^1];~i;--i) (f[x][i]+=f[x][i-1]*(c[x][a[x]^1]-(i-1))%mod)%=mod;
}
int C(int n,int m) {
    if(n<m) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int fp(int a,int b) {
    int c=1;
    for(;b;a=a*a%mod,b>>=1) if(b&1) c=c*a%mod;
    return c;
}
void init() {
    fac[0]=inv[0]=1;
    rep(i,1,m) fac[i]=fac[i-1]*i%mod;
    inv[m]=fp(fac[m],mod-2);
    per(i,m-1,1) inv[i]=inv[i+1]*(i+1)%mod;
}
signed main() {
    n=read();
    m=n>>1;
    scanf("%s",s+1);
    rep(i,1,n-1) {
        int x=read(), y=read();
        add(x,y), add(y,x);
    }
    rep(i,1,n) a[i]=s[i]-'0';
    dp(1,0);
    init();
    rep(i,0,m) G[i]=f[1][i]*fac[m-i]%mod;
    rep(i,0,m) rep(j,i,m) {
        int c=((j-i)&1)? -1:1;
        (F[i]+=c*C(j,i)%mod*G[j]%mod)%=mod;
        if(F[i]<0) F[i]+=mod;
    }
    rep(i,0,m) printf("%lld\n",F[i]);
}

觉得这篇文章怎么样？

点个赞，让更多人看到！

分享这篇文章

知识因分享而增值

Twitter Telegram 微博 QQ Facebook LinkedIn

分类

Record

标签

DP
树形DP
计数
容斥原理
二项式反演
状态压缩
边双连通分量

版权声明：本文作者为 Nanami^2，首发于nanami7.top。

遵循 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

评论区

本评论区由 EveSunMaple 自主开发