【仙人掌+树形dp】仙人掌

传送仙人掌:UOJ190

ZJOI2017


讲道理这道题我考场上可能是爆0了。。。(读优写挂我也是很无奈,不然30分)

先放一张萌萌哒仙人掌(这似乎是这个hexo主题的图,是不是很搭)

cactus

思路:终于进入正题

  • 链的做法还是比较sb的,dp可做,直接找规律也是可以的,反正是2的幂次。
    • 然后考虑树的做法,两点$(u,v)$之间的连边可以看作是一条覆盖了$(u,lca(u,v)),(v,lca(u,v))$的链
    • 可以发现这道题有一个要求是没有重边,这个性质可就厉害了。可以发现在一个合法的仙人掌(合法的答案),一定是原树上的每条边要么被长度>2的链覆盖,要么不被覆盖。 可以把不覆盖强行当做是被长度为1的链覆盖,因为实际上不存在长度为1的链,所以计数上不会有影响。 这样题意就转化为了求用链恰好覆盖整棵树一次的方案数。
    • 考虑树形dp,用$f_i$表示i(i不为根)及其子树的边和父边被覆盖且恰有一条链连向子树外某点的方案数(不考虑连向外面的是哪个点):
      • 为什么这么设计状态呢?可以发现对于一棵不是根节点i及其子树,子树内(包括i)总有且一条链是连向子树外的。如果不连出去,i所对应的父边就不被覆盖了;如果连出去多条,i所对应的父边就被多次覆盖。
      • 那么怎么$f_i$转移呢?
      • 首先i的子树是相对独立的,换句话说每棵子树内部的连边与其他子树无关,每棵子树只有连出去的边才能与其他子树连边或是连到i的外面。考虑到$f_i​$的意义,若干棵子树中必须选出一棵来连向i子树的外面,其余的一部分连向i,另一部分相互两两配对。可以发现最终配对的结果与只与子树的棵树有关。
      • 那么$f_i = k\times g_{k-1} \times \prod\limits_{j\in child(i)} f_j$,其中k表示i的子树的棵树;
      • $g_k$表示的k条边在内部两两配对或连到i的方案数,那么k-1是因为一条边强制连到外面
      • $g_k=g_{k-1}+g_{k-2}\times(k-1)$,因为新加进来的边连到根节点的贡献是$g_{k-1}$,配对的话要挑出一条已有的边来配对,贡献是$g_{k-2}\times(k-1)$,这个可以预处理一发。
      • 根的话不用连出去,自己推一下。
    • 至此树的dp没了。
    • 可能是假的,因为这个dp方程显然可以直接分解成乘法,$ans=\prod g_x$。讲道理我是看UOJ上的代码发现的。
    • 然后考虑仙人掌,如果不是仙人掌那显然是GG的。特判一发。
    • 是仙人掌的话可以发现环上的边是没有救的。
    • 所以把环边删掉以后仙人掌就变成了森林,乘法原理。
    • 重点可能是找仙人掌吧!

注意:取模不要忘,预处理注意时间啊(题目有说t很大然而我瞎)


还是贴代码吧:

正常树形dp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 2200000
#define mo 998244353
LL t,n,m,x,y,tot,head[N],f[N],g[N],fa[N],mark[N];
bool vis[N],vis2[N];
struct edge{LL v,nxt;}e[N];
LL getint(){
char ch; LL sum=0;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
return sum;
}
void add(LL x,LL y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void init(LL n){tot=1; for (int i=1;i<=n;i++){vis[i]=head[i]=mark[i]=fa[i]=vis2[i]=0; f[i]=1;}}
bool dfs(int u){//判定仙人掌+标记环边
vis[u]=1;
for (int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if (v==fa[u]) continue;
if (!vis[v]){fa[v]=u; if (dfs(v)) return 1;}
else{
e[i^1].v=fa[v];//防止找到环以后反着又找到了
for (int k=u;k!=v;k=fa[k]){
if (mark[k]) return 1; else mark[k]=1;//已经到过的环GG
}
}
}
return 0;
}
void dp(LL u){
int sum=0; vis2[u]=1;
for (int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if (fa[u]==v || vis2[v]) continue;
dp(v);
if (!mark[v]){sum++; f[u]=f[u]*f[v]%mo;}
}
if (sum!=0){
if (fa[u]==0 || mark[u]) f[u]=f[u]*g[sum]%mo;//某棵树的根
else f[u]=f[u]*(g[sum-1]*sum%mo+g[sum])%mo;//某棵树的子树的根
}
}
int main(){
t=getint();
while (t--){
n=getint(); m=getint();
init(n);
g[0]=g[1]=1; for (int i=2;i<=n;i++) g[i]=(g[i-1]+g[i-2]*(i-1))%mo;//预处理
for (int i=1;i<=m;i++){
x=getint(); y=getint();
add(x,y); add(y,x);
}
if (dfs(1)){puts("0"); continue;};
dp(1); LL ans=f[1];
for (int i=2;i<=n;i++) if (mark[i]) ans=ans*f[i]%mo;
printf("%lld\n",ans);
}
return 0;
}

强行换成乘法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 2200000
#define mo 998244353
LL t,n,m,x,y,tot,head[N],cnt[N],g[N],fa[N],mark[N];
bool vis[N];
struct edge{LL v,nxt;}e[N];
LL getint(){
char ch; LL sum=0;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
return sum;
}
void add(LL x,LL y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void init(LL n){tot=1; for (int i=1;i<=n;i++) vis[i]=head[i]=mark[i]=fa[i]=cnt[i]=0;}
bool dfs(int u){
vis[u]=1;
for (int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if (v==fa[u]) continue;
if (!vis[v]){fa[v]=u; if (dfs(v)) return 1;}
else{
e[i^1].v=fa[v];
for (int k=u;k!=v;k=fa[k]){
if (mark[k]) return 1; else mark[k]=1;
}
}
}
return 0;
}
int main(){
t=getint();
while (t--){
n=getint(); m=getint();
init(n);
g[0]=g[1]=1; for (int i=2;i<=n;i++) g[i]=(g[i-1]+g[i-2]*(i-1))%mo;
for (int i=1;i<=m;i++){
x=getint(); y=getint();
add(x,y); add(y,x);
}
if (dfs(1)){puts("0"); continue;};
for (int i=2;i<=n;i++) if (!mark[i]){cnt[i]++; cnt[fa[i]]++;}//统计子节点个数
LL ans=1;
for (int i=1;i<=n;i++) ans=ans*g[cnt[i]]%mo;//每个节点本身的贡献实际上是子节点的个数带来的
printf("%lld\n",ans);
}
return 0;
}