「WC 2019」数树

Problem

Description

对于两棵树 T_{1}, T_{2} ,定义它们的交 T_{1} \cap T_{2} T_{1} T_{2} 的边集的交形成的森林。
对于某一森林 T ,定义 \operatorname{cc}{(T)} 为森林 T 中的连通块个数。
现要求完成指定的以下三个任务之一:

  1. 给定 y, n, T_{1}, T_{2} ,求 y^{\operatorname{cc}{\left(T_{1} \cap T_{2}\right)}}
  2. 给定 y, n, T_{1} ,求 \sum_{\left|V(T_{2})\right| = n} y^{\operatorname{cc}{\left(T_{1}\cap{T_{2}}\right)}}
  3. 给定 y, n ,求 \sum_{\left|V(T_{1})\right| = n}\sum_{\left|V(T_{2})\right| = n}y^{\operatorname{cc}{\left(T_{1}\cap{T_{2}}\right)}}

答案对 998244353 取模。

Constraints

3\le n\le 10^{5}, \left|V(T_{1})\right| = \left|V(T_{2})\right| = n

Solution

Analysis

对于某一棵树 T ,默认其根为编号为 1 的节点。
易知对于某一森林 T ,显然有 \operatorname{cc}{(T)} = \left|V(T)\right| - \left|E(T)\right|
以下记 V_{x} := V(T_{x}), E_{x} := E(T_{x})

task0

直接并查集即可,时间复杂度 O(n)

task1

y = 1 时,易知答案为 n^{n - 2} ,故以下假设 y \ne 1

由容斥原理有:

f(S) = \sum_{S' \subseteq S} \sum_{S'' \subseteq S'} (-1)^{|S'| - |S''|} f\left(S''\right)

代入 f(S) = y^{n - |S|}, S = E_{1}\cap{E_{2}} ,有:

\begin{aligned} \sum_{|V_{2}| = n}y^{n-\left|E_{1}\cap{E_{2}}\right|} &= \sum_{|V_{2}| = n} \sum_{E\subseteq{E_{1} \cap{E_{2}}}} \sum_{E'\subseteq{E}} (-1)^{|E|-|E'|} y^{n-|E'|} \\ &= \sum_{E\subseteq{E_{1}}}\left( \sum_{E'\subseteq{E}}(-1)^{|E|-|E'|}y^{n-|E'|}\right) \sum_{|V_{2}| = n}\left[E\subseteq{E_{2}}\right] \\ &= \sum_{E\subseteq{E_{1}}}y^{n-|E|}\left( \sum_{E'\subseteq{E}}(-y)^{|E|-|E'|}\right) \sum_{|V_{2}| = n}\left[E\subseteq{E_{2}}\right] \\ &= \sum_{E\subseteq{E_{1}}}y^{n-|E|}(1 - y)^{|E|} \sum_{|V_{2}| = n}\left[E\subseteq{E_{2}}\right] \end{aligned}

考虑如何计算 \sum_{|V_{2}| = n}\left[E\subseteq{E_{2}}\right] ,容易发现其即为在 E 中加边使得 T=(V_{2}, E) 成为一棵树的方案数。

设森林 T=(V_{2}, E) 中的 k 个连通块大小分别为 a_{1},a_{2},...,a_{k} ,则将原有的连通块缩成一个点,根据 prufer 序列易有:

\begin{aligned} \sum_{|V_{2}| = n}\left[E\subseteq{E_{2}}\right] &=\sum_{\substack{\left|\left\{p_{i}\right\}\right| = k - 2 \\ 1 \le p_{i} \le k}} \prod_{i = 1}^{k} a_{i}^{1+\sum_{j = 1}^{k-2} [p_{j} = i]} \\ &=\left(\prod_{i = 1}^{k}a_{i}\right)\sum_{\substack{\left|\left\{p_{i}\right\}\right| = k - 2 \\ 1 \le p_{i} \le k}}\prod_{i = 1}^{k-2}a_{p_{i}} \\ &=\left(\prod_{i = 1}^{k}a_{i}\right)\prod_{i = 1}^{k-2}\sum_{j = 1}^{k}a_{j} \\ &=\left(\prod_{i = 1}^{k}a_{i}\right)n^{k-2} \end{aligned}

而显然 k=n-|E| ,于是有:

\begin{aligned} \sum_{|V_{2}| = n}y^{n-\left|E_{1}\cap{E_{2}}\right|} &=\sum_{E\subseteq{E_{1}}}y^{n-|E|}(1 - y)^{|E|}n^{n-|E|-2}\prod_{i = 1}^{n-|E|}a_{i} \\ &=\frac{(1 - y)^{n}}{n^{2}}\sum_{E\subseteq{E_{1}}}\left(\frac{ny}{1 - y}\right)^{n-|E|}\prod_{i = 1}^{n-|E|}a_{i} \\ &=\frac{(1 - y)^{n}}{n^{2}}\sum_{E\subseteq{E_{1}}}\prod_{i = 1}^{n-|E|}\frac{ny}{1 - y}a_{i} \end{aligned}

此处记 \displaystyle{k = \frac{ny}{1 - y}} ,则相当于每个大小为 s 的连通块会产生 ks 的贡献。

考虑 DP。
定义一种方案的权值为该方案中所有连通块的 ks 之和。
容易发现在考虑以点 u 为根的子树时不能直接将点 u 所在的连通块的权值计入答案,因为点 u 所在的连通块还有可能会与 u 的父节点相连,故当前根节点所在连通块大小应作为状态的一维。
则设 f_{u,s} 为在只考虑以点 u 为根的子树的情况下满足点 u 所在连通块大小为 s 的所有方案去掉点 u 所在连通块之后的权值之和。
那么现在答案即为 k\sum_{s = 1}^{n} s f_{1,s}

考虑如何转移。
显然可以通过树上背包达到 O(n^{2}) 的复杂度,但其无法通过本题。
容易发现背包的转移是一个卷积的形式,于是固定状态的第一维对第二维建立幂级数,即 F_{u}(x)=\sum_{s}f_{u,s}x^{s}
又发现转移时一个儿子 v 贡献的常数项为以其为根的子树的答案即 k\sum_{s}sf_{v,s} ,于是记 g_{u}=k\sum_{s}sf_{u,s}=kF'(1) ,则有:

F_{u}(x)=x\prod_{v\in\operatorname{son}{(u)}}\left(g_{v}+F_{v}(x)\right)

则有:

\begin{aligned} g_{u} &=kF'(1) \\ &=k\left(\prod_{v\in\operatorname{son}{(u)}} (g_{v}+F_{v}(1)) +\sum_{v\in\operatorname{son}{(u)}}F_{v}'(1)\prod_{w\in\operatorname{son}{(u)},v\ne w}\left(g_{w}+F_{w}(1)\right)\right) \\ &=k\left(\prod_{v\in\operatorname{son}{(u)}} (g_{v}+F_{v}(1)) +\left(\prod_{v\in\operatorname{son}{(u)}} (g_{v}+F_{v}(1)) \right)\sum_{v\in\operatorname{son}{(u)}}\frac{F_{v}'(1)}{g_{v}+F_{v}(1)}\right) \\ &=\left(\prod_{v\in\operatorname{son}{(u)}} (g_{v}+F_{v}(1)) \right)\left(k+\sum_{v\in\operatorname{son}{(u)}}\frac{g_{v}}{g_{v}+F_{v}(1)}\right) \\ &=F_{u}(1)\left(k+\sum_{v\in\operatorname{son}{(u)}}\frac{g_{v}}{g_{v}+F_{v}(1)}\right) \end{aligned}

h_{u}=F_{u}(1)=\sum_{s}f_{u,s} ,则有:

\begin{aligned} g_{u} &= h_{u}\left(k+\sum_{v\in\operatorname{son}{(u)}}\frac{g_{v}}{g_{v}+h_{v}}\right) \\ h_{u} &= \prod_{v\in\operatorname{son}{(u)}}(g_{v}+h_{v}) \end{aligned}

于是可以直接递推,时间复杂度 O(n)

task2

y=1 时,易知答案为 n^{2n-4} ,故以下假设 y\ne 1

仿照 task1 可以知道答案即为:

\begin{aligned} \sum_{|V_{1}| = n}\sum_{|V_{2}| = n} y^{\operatorname{cc}{\left(T_{1}\cap{T_{2}}\right)}} &= \sum_{\left|V\right| = n}y^{n-|E|}(1 - y)^{|E|}\sum_{|V_{1}| = n}\left[E\subseteq{E_{1}}\right]\sum_{|V_{2}| = n}\left[E\subseteq{E_{2}}\right] \\ &= \frac{(1 - y)^{n}}{n^{4}}\sum_{\left|V\right| = n} \prod_{i = 1}^{n-|E|} \frac{n^{2}y}{1 - y}a_{i}^{2} \end{aligned}

考虑枚举 T 中的连通块个数及大小。

记连通块个数为 k k 个连通块的大小分别为 a_{1},a_{2},...,a_{k} ,则易知满足条件的森林数量为 \prod_{i = 1}^{k}a_{i}^{a_{i}-2}
又因连通块顺序对答案没有影响,故还需除以连通块的排列方案数 k! ,算上选出 k 个连通块的方案数 \displaystyle{\frac{n!}{\prod_{i = 1}^{k}a_{i}!}} ,有:

\begin{aligned} \frac{(1 - y)^{n}}{n^{4}}\sum_{\left|V\right| = n}\prod_{i = 1}^{n-|E|}\frac{n^{2}y}{1 - y}a_{i}^{2} &= \frac{(1 - y)^{n}n!}{n^{4}}\sum_{k = 1}^{n}\frac{1}{k!}\sum_{\substack{a_{1}+a_{2}+...+a_{k} = n \\ a_{i} > 0}}\prod_{i = 1}^{k}\frac{n^{2}y}{(1 - y)a_{i}!}a_{i}^{a_{i}} \\ &= \frac{(1 - y)^{n}n!}{n^{4}}[x^{n}]\sum_{k = 1}^{n}\frac{1}{k!}\left(\frac{n^{2}y}{1 - y}\sum_{a>0}\frac{a^{a}}{a!}x^{a}\right)^{k} \\ &= \frac{(1 - y)^{n}n!}{n^{4}}[x^{n}]\exp{\left(\frac{n^{2}y}{1 - y}\sum_{a>0}\frac{a^{a}}{a!}x^{a}\right)} \end{aligned}

于是使用多项式 \exp 即可解决,时间复杂度 O(n \log{n})

Code

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
#include<set>
#include<cstdio>
#include<cassert>
#include<algorithm>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(100000);
constexpr int p(998244353);

template<typename x_tp,typename y_tp>
inline void inc(x_tp&x,const y_tp&y)
{x+=y;(p<=x)&&(x-=p);}
template<typename x_tp,typename y_tp>
inline void dec(x_tp&x,const y_tp&y)
{x-=y;(x<0)&&(x+=p);}

template<typename x_tp,typename y_tp>
inline int pls(const x_tp&x,const y_tp&y)
{return(x+y<p)?x+y:(x+y-p);}
template<typename x_tp,typename y_tp>
inline int sub(const x_tp&x,const y_tp&y)
{return(x<y)?x-y+p:(x-y);}

template<typename _Tp>
inline int fpow(_Tp v,int n){
int pw=1;
for(;n;n>>=1,v=(i64)v*v%p)
if(n&1)pw=(i64)pw*v%p;
return pw;
}

template<typename _Tp>
inline void swap(_Tp&x,_Tp&y)
{_Tp z=x;x=y;y=z;}

template<typename x_tp,typename y_tp>
inline int divp(const x_tp&x,const y_tp&y)
{return(i64)x*fpow(y,p-2)%p;}

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;

namespace task0{
std::set<std::pair<int,int>>s;

inline void solve(const int&n,const int&y){
for(int i=n-1,u,v;i!=0;--i)
if(u=io,v=io,u<v)
s.insert(std::make_pair(u,v));
else
s.insert(std::make_pair(v,u));

int cnt=n;
for(int i=n-1,u,v;i!=0;--i)
if(u=io,v=io,u<v)
s.count(std::make_pair(u,v))&&--cnt;
else
s.count(std::make_pair(v,u))&&--cnt;

printf("%d\n",fpow(y,cnt));
}
}

namespace task1{
struct Edge{
int v;Edge*las;

inline Edge* init(const int&to,Edge*const&ls)
{return v=to,las=ls,this;}
}*las[maxn+1];

inline void lnk(const int&u,const int&v){
static Edge pool[maxn<<1],*alc=pool-1;
las[u]=(++alc)->init(v,las[u]);
las[v]=(++alc)->init(u,las[v]);
}

int g[maxn+1],
h[maxn+1];

int k;
void calc(const int&u,const int&fa){
int ch=1,sum=k;
for(Edge*o=las[u];o;o=o->las)
if(o->v!=fa){
calc(o->v,u);
ch=(i64)ch*pls(g[o->v],h[o->v])%p;
inc(sum,divp(g[o->v],pls(g[o->v],h[o->v])));
}
h[u]=ch;
g[u]=(i64)ch*sum%p;
}

inline void solve(const int&n,const int&y){
if(y==1)
return printf("%d\n",fpow(n,n-2)),void();

k=divp((i64)n*y%p,sub(1,y));
for(int i=n-1;i!=0;--i)
lnk(io,io);
calc(1,0);
printf("%d\n",(i64)g[1]*fpow(sub(1,y),n)%p*fpow(n,p-3)%p);
}
}

namespace task2{
constexpr int mxdg(262144);
constexpr int proot(3);

using Z=int;
using mZ=i64;

using poly_t=Z[mxdg];
using poly=Z*const;

poly_t wn,iwn,inv;

inline int calcpw2(const int&n){
int t=1;
for(;t<n;t<<=1);
return t;
}

inline void polyinit(){
const Z wnv=fpow(proot,(p-1)/mxdg),
iwnv=fpow(wnv,p-2);
Z w=1,iw=1;
wn[0]=iwn[0]=1;
for(int i=1;i!=mxdg;++i){
w=(mZ)w*wnv%p;wn[i]=w;
iw=(mZ)iw*iwnv%p;iwn[i]=iw;
}

inv[0]=inv[1]=1;
for(int i=2;i!=mxdg;++i)
inv[i]=(i64)inv[p%i]*(p-p/i)%p;
}

void DFT(poly&a,const int&n){
for(int i=0,j=0;i!=n;++i){
if(i<j)swap(a[i],a[j]);
for(int k=n>>1;(j^=k)<k;k>>=1);
}
poly&endpos=a+n;
for(int l=1,tp=mxdg>>1;l!=n;l+=l,tp>>=1)
for(Z*i=a,*w,z;i!=endpos;i+=l+l)
for(int j=(w=wn,0);j!=l;++j,w+=tp)
z=(mZ)i[j+l]**w%p,
i[j+l]=sub(i[j],z),
inc(i[j],z);
}
void IDFT(poly&a,const int&n){
for(int i=0,j=0;i!=n;++i){
if(i<j)swap(a[i],a[j]);
for(int k=n>>1;(j^=k)<k;k>>=1);
}
poly&endpos=a+n;
for(int l=1,tp=mxdg>>1;l!=n;l+=l,tp>>=1)
for(Z*i=a,*w,z;i!=endpos;i+=l+l)
for(int j=(w=iwn,0);j!=l;++j,w+=tp)
z=(mZ)i[j+l]**w%p,
i[j+l]=sub(i[j],z),
inc(i[j],z);

const Z invn=fpow(n,p-2);
for(Z*i=a;i!=endpos;++i)
*i=(mZ)*i*invn%p;
}

inline void cp(const poly&sl,const poly&sr,poly&tl,poly&tr){
std::copy(sl,sr,tl);
if(sr-sl<tr-tl)
std::fill(tl+(sr-sl),tr,0);
}

void polyder(const poly&h,poly&f,const int&n){
for(int i=1;i!=n;++i)
f[i-1]=(mZ)h[i]*i%p;
f[n-1]=0;
}

void polyint(const poly&h,poly&f,const int&n){
for(int i=n-1;i!=0;--i)
f[i]=(mZ)h[i-1]*inv[i]%p;
f[0]=0;
}

void polyinv(const poly&h,poly&f,const int&n){
static poly_t inv_t;
std::fill(f,f+n+n,0);
f[0]=fpow(h[0],p-2);
for(int t=1;(1<<t)<=n;++t){
const int n1(1<<t),n2(n1<<1);
cp(h,h+n1,inv_t,inv_t+n2);

DFT(f,n2);DFT(inv_t,n2);
for(int i=0;i!=n2;++i)
f[i]=(mZ)f[i]*sub(2,(mZ)inv_t[i]*f[i]%p)%p;
IDFT(f,n2);

std::fill(f+n1,f+n2,0);
}
}

void polyln(const poly&h,poly&f,const int&n){
static poly_t ln_t;
assert(h[0]==1);
const int n2(n<<1);

polyder(h,f,n);
std::fill(f+n,f+n2,0);
polyinv(h,ln_t,n);

DFT(f,n2);DFT(ln_t,n2);
for(int i=0;i!=n2;++i)
f[i]=(mZ)f[i]*ln_t[i]%p;
IDFT(f,n2);

polyint(f,f,n);
std::fill(f+n,f+n2,0);
}

void polyexp(const poly&h,poly&f,const int&n){
static poly_t exp_t;
assert(h[0]==0);
std::fill(f,f+n+n,0);
f[0]=1;
for(int t=1;(1<<t)<=n;++t){
const int n1(1<<t),n2(n1<<1);

polyln(f,exp_t,n1);
exp_t[0]=sub(h[0]+1,exp_t[0]);
for(int i=1;i!=n1;++i)
exp_t[i]=sub(h[i],exp_t[i]);
std::fill(exp_t+n1,exp_t+n2,0);

DFT(f,n2);DFT(exp_t,n2);
for(int i=0;i!=n2;++i)
f[i]=(mZ)f[i]*exp_t[i]%p;
IDFT(f,n2);

std::fill(f+n1,f+n2,0);
}
}

poly_t h,f;
inline void solve(const int&n,const int&y){
if(y==1)
return printf("%d\n",fpow(n,n+n-4)),void();
polyinit();

const int k(divp((i64)n*n%p*y%p,sub(1,y)));
int iv=1;
for(int i=1;i<=n;++i)
iv=(i64)iv*inv[i]%p,
h[i]=(i64)fpow(i,i)*iv%p*k%p;
polyexp(h,f,calcpw2(n+1));

printf("%d\n",(i64)f[n]*fpow(iv,p-2)%p*fpow(sub(1,y),n)%p*fpow(inv[n],4)%p);
}
}

int main(){
const int n=io,y=io,op=io;

if(op==0)
task0::solve(n,y);
else if(op==1)
task1::solve(n,y);
else
task2::solve(n,y);

return 0;
}