「NOIP Record」#1 树形DP(1)

树形 DP 计数。

luogu8867 建造军营

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

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

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

还要乘上 $x$ 所在边双中任意选择的方案数,并且减掉子树中一个都不选的方案。$$f_x = 2^{c_x} \prod_{y \in son(x)} (f_y+2^{sz_y}) – 2^{sz_x-1}$$但这样求出的并不是答案。

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

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

非法方案是 $x$ 没有建造军营,并且只有一个儿子 $y$ 所在子树中建造了,容易得到这部分就是$$2^{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)

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

  • 首先如果一个节点是初始为 $0$ 的 $\text{AND}$ 型节点或者初始值为 $1$ 的 $\text{OR}$ 型节点,那么一定不会改变自身的颜色。称其为黑点,其他成为白点。
  • 白点最多变化一次。
  • 同一个初始权值白色连通块内,要么权值都变化一次,要么都不变。证明略。
  • 那么一个白色连通块何时才不会改变权值呢?只需要考虑它周围的一圈黑点。如果是 $(0,\text{AND})$ 与 $(0,\text{OR})$,$(1,\text{OR})$ 与 $(1,\text{AND})$,那么右边就不会因为左边改变权值,而两个不同类型的白点 $(1,\text{AND})$ 与 $(0,\text{OR})$ 或者一黑一白是会影响对方的。因此推出一个白色连通块的权值不改变,当且仅当整个连通块以及周围的一圈黑点,权值都相同。
  • 如何让一个白色连通块达到权值相同?需要满足以下两个条件之一。1. 连通块内存在一个白点,满足初始权值等于最终权值。2. 周围存在一个黑点,满足其与这个连通块的最终权值相同。

考虑用树形 DP 来做。

为了方便采用如下标记

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

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

首先 $q$ 和 $r$ 就存在非法组合。

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

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

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

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

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

开个临时数组 $g$。

对于 $x$ 和 $y \in son(x)$,如果 $a_x = a_y$

$$g_0 = f_{x,0} \cdot (f_{y,0} + f_{y,1})$$

$$g_1 = f_{x,1} \cdot (f_{y,0} + f_{y,1} + f_{y,2} + f_{y,3})$$

$$
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})
$$

$$
g_3 = f_{x,3} \cdot f_{y,3}
$$

若 $a_x \neq a_y$

$$g_0 = 0$$

$$g_1 = f_{x,1} \cdot (f_{y,1} + f_{y,2})$$

$$
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})
$$

$$
g_3 = f_{x,3} \cdot f_{y,1}
$$

然后 $$ f_x \leftarrow g$$ 答案是 $f_{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』 继续深潜,为了同一个梦想

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

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

考虑一个转化,求 $ans_i$ 时,将 $i$ 钦定为根。那么前者转化为子树内到达 $i$ 的链。

设 $f_r(x)$ 为整棵树以 $r$ 为根,在以 $x$ 为根的子树内,有多少以 $x$ 为端点且满足条件的的链,其实就是在子树内除了 $x$ 选择至少一个节点的方案数。$$f_{r}(x) = \sum_{y \in son(x)} (2f_r(y) +1)$$然后考虑第二种情况,其实就是两条上述的链拼凑而成,

设 $S = f_r(x)$,$F(x) = 2f_r(x)+1$。

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

综上,得到以 $r$ 为整棵树的根时,以 $x$ 为根的子树内的答案 $g_r(x)$。

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

发现对于 $(x,y)$,有$$f_y(x) = f_x(x) – F(y)$$$$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

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

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

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

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

为了避免包含等不必要的麻烦,设 $S_x$ 为以 $x$ 为根的子树中,不含 $x$ 的颜色集合。同时设 $S_1 \otimes S_2$ 表示 $S_1$ 中任意元素并上 $S_2$ 中任意元素结果为同一种颜色,且满足 $S_1 \otimes S_2 = S_1 \otimes S_1$。

设 $f_{x,i,S}$ 为以 $x$ 为根的子树,$x$ 的颜色是 $i$,其他子树内的颜色集合是 $S$ 的方案数。

考虑 $f_{y,j,S_0}$ 如何转移。

条件是 $T=S_0 \cup {j}$,存在 $S$ 满足 $S \otimes T = i$,贡献为$$f_{y,j,S_0} \cdot f_{x,i,S} \rightarrow f’_{x,i,S|T}$$

特别地,对于 $x$ 的第一棵子树$$f_{y,j,S_0} \rightarrow f_{x,i,S_0 \cup {j}}$$ 复杂度 $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();
}
  • 状态压缩,优先使用刷表法
  • 考虑再三后再预处理
  • 预处理时一定不要把初始状态设成无解状态
  • 加入子树的计数思路
  • 一开始竟然设 $S_x$ 为以 $x$ 为根的子树的所有颜色,导致很多麻烦且干扰思路与转移。

最后附上我一开始写的 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]小星星

题意比较裸。

设 $f_{x,i,G_0}$ 为以 $x$ 为根的子树,节点 $x$ 映射到原图中的 $i$,此时子树内映射到图中的节点集合为 $G_0$ 的方案数。

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

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

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

考虑此时如何求方案数。设 $f_{x,i}$ 表示以 $x$ 为根的子树,节点 $x$ 映射到了图中节点 $i$ 的方案数,容易写出$$f_{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)$,求对于 $x=1,2,\ldots,n$,所有 $V$ 的子集与 $E$ 构成的图中,恰好有 $x$ 个连通块的方案数。对 $998244353$ 取模。

$n \le 5000$

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

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

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

如果 $x$ 不选择,那么对于子节点 $y$,其选不选都不收影响,因此$$f_{x,j,0} \cdot (f_{y,k,0}+f_{y,k,1}) \rightarrow g_{j+k,0}$$ 如果 $x$ 选择,那么如果 $y$ 选择了,就会减少一个连通块$$f_{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

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

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

设当前加入了 $cnt$ 棵子树,那么在合并子树的过程中,最少剩下 $cnt+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 提高组] 游戏

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

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

设 $f_{x,i}$ 为以 $x$ 为根的子树,有 $i$ 个回合没有平的方案数。

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

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

#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]);
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇