OI - Bracket Sequences on Tree (HDU) | Lucky_Glass's Blog
0%

OI - Bracket Sequences on Tree (HDU)

出题人你卡 hash 卡得开心吗?


Part1. 题面

本题有多组数据,总共 $t$ 组。

每组数据给出一棵 $n$ 个点的无根树,求从任意点出发可能得到的本质不同的括号序列数量,对 $998244353$ 取模。

> Tip
一棵树的括号序列为:从根节点出发 DFS,当一个点进入 DFS 栈中时,在序列的末尾加上 (,当一个点从 DFS 栈中弹出时,在序列末尾加上 )
这样可以得到一个长度为 2n 的括号序列。
本质不同的括号序列即指长得不一样的括号序列。

数据结构:$1\le t\le10^5,1\le n\le10^5$;保证所有数据点的 $n$ 之和不超过 $3.2\times10^6$。


Part2. 解析

首先你得知道什么叫树的同构:

> Tip
如果两棵树可以通过给节点重新编号,使得两棵树对应边的节点编号相同,则称这两棵树同构。

Part2/1. 指定某点为根的答案

不妨指定 1 为根。(万年工具人 1 号节点……)

可以直接 dp:u 的子树中的括号序列数量为 f[u]

> Tab
cntch[u] 为 u 的子节点数量;
fac[i] 为模意义下的 $i!$。

先计算出每个子节点的答案 f[v]

  1. f[u] 应该为所有 f[v] 的乘积(因为是方案数,所以通过乘法原理计算);

  2. DFS 子树的顺序也会造成影响,所以要乘上子树的全排列,即乘上 fac[cntch[u]]

  3. 不难发现,同构的两棵树的括号序列的方案集合一定是一样的,因此有一些会算重复;

    把同构的子树划分到一块,计算出每一块的大小,为 $\{sam_1,sam_2,…,sam_t\}$,那么最后应该除以 $\prod_{i=1}^t(sam_i)!$。(其实就是可重集的全排列)

最后得到的转移式(要在模意义下计算):

Part2/2. 换根DP求树的同构

(这也是最近学习的内容 awa)

仍然先考虑指定 1 号节点为根,求出树的一个 hash 值。可以考虑这样设计一个 hash 的递归式:

> Tab
以下默认以 1 为整棵树的根

$idx_u$ 表示以 u 为根的子树的 hash 值。对于叶子节点 $idx_u=1$;其他节点的计算方式为 $idx_u=1+\sum_{v}idx_v\times rand_{siz_v}$,其中 $rand$ 是一开始随机化得到的一个数列,$siz_v$ 是以 v 为根的子树的大小。这样可以一次 DFS 求出每个点的 $idx$。

为什么这样设计 hash?当然目的是要让它的冲突尽可能少。理论上当 $rand$ 数列取质数数列的时候可以尽可能地避免冲突,但是我们需要的 $rand$ 比较多,找质数序列反而麻烦了,于是交给随机化。:)

这样我们就求得了这棵树以 1 为根的 hash 值,但是我们发现当这棵树以不同的点作为根时,hash 值可能不同。为了相对准确地判断树的同构,我们可以在求出以 1 为根的 $idx$ 的基础上,通过 换根DP 计算出以每一个点 $u$ 为根的 $idx’_u$ 。

考虑从当前的根 $u$ 将根换到子节点 $v$。换根DP的核心就是“一次换根只会影响 u 和 v 的DP值”,显然 $idx_u’$ 是满足这个特点的。

考虑从 u 到 v 的转移:
jpg1

我们已经计算出了 $idx’_u$,要计算 $idx_v’$。发现 v 的子树内的 $idx_v$ 并没有改变,换根后,u 变为 v 的子节点。首先 u 要减去原来 v 对 $idx_u’$ 的贡献:$rand_{siz_v}\times idx_v$,然后 v 要加上 u 的贡献 $(idx_u’-rand_{siz_v}\times idx_v)\times rand_{n-siz_v}$($n-siz_v$ 就是现在 u 的子树的大小嘛)。

所以可以得到 $idx’_v=idx_v+(idx_u’-rand_{siz_v}\times idx_{siz_v})\times rand_{n-siz_v}$,最初 $idx’_1=idx_1$,然后就可以 DP 了。

实际上,实现代码时,$idx’_v$ 并没有加上 $idx_v$,而是 $idx’_v=idx_u-rand_{siz_v}\times idx_{siz_v}+rand_{n-siz_u}\times idx_u’$。当要计算以 v 为根的 hash 值时,就计算 $idx’_v\times rand_{n-siz_v}+idx_v$ 即可。

Part2/3. 换根DP求每个点为根的答案

在 Part2/1 ,我们DP计算了以 1 为根的答案,但是显然以不同的点为根,括号序列很有可能是不一样的。

其实和换根DP求 $idx_u’$ 是差不多的,还是定义 $f’_u$ 表示整棵树以 u 为根,能够得到的本质不同的括号序列的数量。主要难点就是“删去 v 对 $f_u’$ 的贡献,并计算新的作为 v 的子节点的 u 的贡献”。

记删去 v 对 $f’_u$ 的贡献后,u 作为 v 的子节点代表的子树中括号序列的数量为 $h$。最初将 $h$ 的值设为 $f’_u$

要删除贡献,首先要知道 $f_u’$ 是怎么计算的:

jpg2

  1. v 不是 u 的子树了,要除去 $f_v$ 对 $f_u’$ 的贡献,即$\div f_v$;
  2. u 的子树少了一棵:记原来 u 作为根时,有 cnt 棵子树,因为计算的时候 $f_v$ 中乘上了 $cnt!$,现在要改为乘上 $(cnt-1)!$ —— 可以先乘上 $(cnt!)^{-1}$ 再乘上 $(cnt-1)!$ ;
  3. u 的子树中,与 v 同构的子树少了一棵:设原来 u 为根时,与 v 同构的子树有 $sam$ 棵,因为要除去重复,除掉了 $sam!$,现在要改为除掉 $(sam-1)!$ —— 可以先乘上 $sam!$,再乘上 $\left[(sam-1)!\right]^{-1}$;

所以 $h=f_u’\times (f_v)^{-1}\times (cnt!)^{-1}\times(cnt-1)!\times sam!\times (sam-1)!$;这样 u 作为 v 的子树时的括号序列数量就求到了。

然后计算 $f_v’$,先设 $f_v’$ 的初值为 $f_v$:(仍然是这张图)

jpg1

  1. u 作为 v 的子树,提供了 $h$ 的贡献,则乘上 $h$;
  2. v 的子树多了一个,记原来子树个数为 $cnt_v$,因为全排列时乘上了 $cnt_v!$,现在要乘上 $(cnt_v+1)!$,所以乘上 $(cnt_v+1)$ 即可;
  3. v 的与 u 同构的子树增加了一个(这里 u 的子树的哈希值就是 $idx_v’$ 了),记原来 u 的与 u 同构的子树个数为 $sam_v$,因为去重时除去了 $sam_v!$,现在要除去 $(sam_v+1)!$ —— 则先乘上 $sam_v!$,再乘上 $[(sam_v+1)!]^{-1}$ 。

可得 $f_v’=f_v\times h\times (cnt_v+1)\times sam_v!\times [(sam_v+1)!]^{-1}$;

Part2/4. 统计答案

已经计算出分别以每个点为根的答案了,似乎直接把 $f_u’$ 加起来就可以了。

但是一样的道理,如果以 u 为根的整棵树与以 v 为根的整棵树形态相同,那么它们的括号序列方案集合一定完全相同,所以只能计算一次。这个就用到整棵树的哈希值。

还好之前已经计算了,以 u 为根的整棵树的哈希值就为 $idx_u+idx’_u\times rand_{n-siz_u}$。所以只要 map 或者 set 判一下重就好了。

> Tip
这道题卡哈希!(好端端的一道哈希题被搞成了一道rp题……)
反正我写了一个三哈希……用结构体打了包,可以参考一下。


Part3. 源代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
/*Lucky_Glass*/
#include<set>
#include<map>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

typedef unsigned long long ull;
typedef unsigned int uint;
const int N=1e5;
const int MOD=998244353;
#define fix(x) (int((x%MOD+MOD)%MOD))

struct MNUM{
int num;
MNUM(){}
MNUM(int _n){num=_n;}
MNUM operator +(const MNUM &B)const{return fix(1ll*num+B.num);}
MNUM operator -(const MNUM &B)const{return fix(1ll*num-B.num);}
MNUM operator *(const MNUM &B)const{return fix(1ll*num*B.num);}
MNUM operator +=(const MNUM &B){return *this=(*this)+B;}
MNUM operator -=(const MNUM &B){return *this=(*this)-B;}
MNUM operator *=(const MNUM &B){return *this=(*this)*B;}
MNUM operator <(const MNUM &B)const{return num<B.num;}
}fac[N+3],ifac[N+3],ansf[N+3],ansg[N+3],ans;

struct TNODE{
int to;TNODE *nxt;
TNODE(){}
TNODE(int _t,TNODE *_n):to(_t),nxt(_n){}
};
struct TREE{
TNODE pol[N*2+3],*head[N+3],*ncnt;
void Init(int n){
ncnt=pol;
for(int u=1;u<=n;u++)
head[u]=NULL;
}
void AddEdge(int u,int v){
TNODE *p=++ncnt,*q=++ncnt;
*p=TNODE(v,head[u]);head[u]=p;
*q=TNODE(u,head[v]);head[v]=q;
}
TNODE* operator [](int id){return head[id];}
}T_;

const ull HASHMOD1=1073790841,HASHMOD2=1073919029,HASHMOD3=2305843009213693951ull;
struct HASH{
ull idx1,idx2,idx3;
HASH(){}
HASH(ull A){idx1=idx2=idx3=A;}
HASH(ull Ix1,ull Ix2,ull Ix3):idx1(Ix1%HASHMOD1),idx2(Ix2%HASHMOD2),idx3(Ix3%HASHMOD3){}
ull& operator [](int id){return id==1? idx1:idx2;}
HASH operator *(const HASH &B)const{return HASH(idx1*B.idx1,idx2*B.idx2,idx3*B.idx3);}
HASH operator -(const HASH &B)const{return HASH(idx1+HASHMOD1-B.idx1,idx2+HASHMOD2-B.idx2,idx3+HASHMOD3-B.idx3);}
HASH operator +(const HASH &B)const{return HASH(idx1+B.idx1,idx2+B.idx2,idx3+B.idx3);}
HASH operator *=(const HASH &B){return *this=(*this)*B;}
HASH operator -=(const HASH &B){return *this=(*this)-B;}
HASH operator +=(const HASH &B){return *this=(*this)+B;}
bool operator <(const HASH &B)const{
if(idx1!=B.idx1) return idx1<B.idx1;
if(idx2!=B.idx2) return idx2<B.idx2;
return idx3<B.idx3;
}
bool operator !=(const HASH &B)const{return idx1!=B.idx1 || idx2!=B.idx2 || idx3!=B.idx3;}
bool operator ==(const HASH &B)const{return idx1==B.idx1 && idx2==B.idx2 && idx3==B.idx3;}
}idxf[N+3],idxg[N+3],rnd[N+3],nidxg[N+3];

int n,cas;
int siz[N+3],cntch[N+3];
set< HASH > cont;
map< HASH,int > per[N+3];

MNUM QPow(MNUM und,int ovr){
MNUM resu(1);
while(ovr){
if(ovr&1) resu*=und;
und*=und;
ovr>>=1;
}
return resu;
}
void DFSf(int u,int fa){
vector< HASH > sav;
idxf[u]=HASH(1);
siz[u]=1;ansf[u]=1;
cntch[u]=0;
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(v==fa) continue;
cntch[u]++;
DFSf(v,u);
siz[u]+=siz[v];
idxf[u]+=rnd[siz[v]]*idxf[v];
ansf[u]*=ansf[v];
sav.push_back(idxf[v]);
per[u][idxf[v]]++;
}
ansf[u]*=fac[cntch[u]];
sort(sav.begin(),sav.end());
int cnt=1;
for(int i=1;i<(int)sav.size();i++)
if(sav[i]!=sav[i-1]){
ansf[u]*=ifac[cnt];
cnt=1;
}
else cnt++;
ansf[u]*=ifac[cnt];
}
void DFSg(int u,int fa){
// cout<<"? "<<u<<" "<<idxf[u].idx2<<endl;
for(TNODE *it=T_[u];it;it=it->nxt){
int v=it->to;
if(v==fa) continue;

idxg[v]=idxf[u]-rnd[siz[v]]*idxf[v]+rnd[n-siz[u]]*idxg[u];

int cntsam=per[u][idxf[v]];
if(u!=1 && idxg[u]==idxf[v]) cntsam++;
int nch=cntch[u];
if(u!=1) nch++;

MNUM resu=ansg[u];
resu*=fac[cntsam];resu*=ifac[cntsam-1];
resu*=ifac[nch];resu*=fac[nch-1];
resu*=QPow(ansf[v],MOD-2);

cntsam=per[v][idxg[v]]+1;
nch=cntch[v]+1;

ansg[v]=ansf[v];
ansg[v]*=resu;
ansg[v]*=ifac[nch-1];ansg[v]*=fac[nch];
ansg[v]*=fac[cntsam-1];ansg[v]*=ifac[cntsam];

DFSg(v,u);
}
HASH rel=idxf[u]+idxg[u]*rnd[n-siz[u]];
if(!cont.count(rel)){
cont.insert(rel);
ans+=ansg[u];
}
}
void Init(){
fac[0]=1;
for(int i=1;i<=N+2;i++) fac[i]=fac[i-1]*i;
ifac[N+2]=QPow(fac[N+2],MOD-2);
for(int i=N+1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1);
}
int main(){
Init();
scanf("%d",&cas);
srand(20192022);
for(int i=0;i<=N+2;i++){
rnd[i][0]=(i? rnd[i][2]:0)+(ull)rand()*(ull)rand();
rnd[i][1]=(i? rnd[i][0]:0)+(ull)rand()*(ull)rand();
rnd[i][2]=(i? rnd[i][1]:0)+(ull)rand()*(ull)rand();
}
while(cas--){
scanf("%d",&n);
cont.clear();
ans=0;
T_.Init(n);
for(int i=1;i<=n;i++){
per[i].clear();
idxf[i]=idxg[i]=nidxg[i]=HASH(0);
ansf[i]=ansg[i]=0;
}
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
T_.AddEdge(u,v);
}
DFSf(1,0);
ansg[1]=ansf[1];
DFSg(1,0);
printf("%d\n",ans.num);
}
return 0;
}

The End

Thanks for reading!

明明一道好好的哈希判断树的同构题为什么非要卡哈希卡成这样…… =_=