Luogu5206 数树

Arahc 11.0
  2022-01-16 08:00 2022-01-16 08:00 创建   2023-09-02 22:53:54 2023-09-02 22:53:54 更新      2.1k 字  11 分钟  

题面

简化题意

  1. 给定两个大小为 nn 的树，点权为 [1,y][1,y]。若两个点在树上都有边，则点权必须相同。求有多少种赋权方案。
  2. 给定一个大小为 nn 的树，求出对于每一种另一个树的情况，第一问答案的和。
  3. 对于每一种两个树的情况，第一问答案的和。

n≤105n\leq 10^5，对 998244353998244353 取模。

题解

根据 prufer 序不难有大小为 nn 的树共有 nn−2n^{n-2} 种。先特判 y=1y=1 的情况。

第一问

直接统计有多少边重合即可。每有一条边重合，都会使一个点从本来所有点权都能选变成只能选一种（即和它相邻的点相同的那种点权），直接统计。

第二问

设 fif_i 表示至少有 ii 条边重合，gig_i 表示恰好 ii 条边重合的方案数，有：

gi=∑j=in−1(−1)j−1(ji)fjg_i = \sum_{j=i}^{n-1} (-1)^{j-1} \binom{j}{i} f_j

答案为：

ans=∑i=0n−1giyn−i=yn∑i=0n−1y−i∑j=in−i(−1)j−i(ji)fj=yn∑j=0n−1(−1)jfj∑i=0j(−1)i(ji)y−i\begin{aligned} ans &= \sum_{i=0}^{n-1} g_iy^{n-i} \\ &=y^n\sum_{i=0}^{n-1} y^{-i} \sum_{j=i}^{n-i} (-1)^{j-i} \binom{j}{i} f_j \\ &=y^n\sum_{j=0}^{n-1} (-1)^j f_j \sum_{i=0}^j (-1)^i\binom{j}{i}y^{-i} \end{aligned}

后面是个二项式定理：

=yn∑j=0n−1(−1)jfj(y−1y)j=yn∑j=0n−1fj(1−yy)j\begin{aligned} &= y^n\sum_{j=0}^{n-1} (-1)^j f_j (\frac{y-1}{y})^j \\ &= y^n\sum_{j=0}^{n-1} f_j (\frac{1-y}{y})^j \end{aligned}

考虑如何求 ff，考虑矩阵树定理，钦定选定 jj 条边，会出现 n−jn-j 个连通块，用 ss 记录其大小：

=yn∑j=0n−1(1−yy)jnn−j−2∏i=1n−jsi=yn∑j=1n(1−y)n−jyj∑{s},∣s∣=j∏i=1jyn1−ysi=(1−y)nn2∑{s},∣s∣=j∏i=1jyn1−ysi\begin{aligned} &= y^n \sum_{j=0}^{n-1} (\frac{1-y}{y})^jn^{n-j-2} \prod_{i=1}^{n-j} s_i \\ &= y^n\sum_{j=1}^n (1-y)^{n-j}y^j \sum_{\{s\},\left|s\right|=j} \prod_{i=1}^j \frac{yn}{1-y}s_i \\ &= \frac{(1-y)^n}{n^2} \sum_{\{s\},\left|s\right|=j} \prod_{i=1}^j \frac{yn}{1-y}s_i \end{aligned}

考虑 ∑\sum 后面的一块如何维护。考虑连通块大小贡献的组合意义，一个大小为 ss 的连通块的贡献，相当于在连通块内任选一个点，这个点产生 yn1−y\frac{yn}{1-y} 的贡献，其他点没有贡献。

记 fi,0/1f_{i,0/1} 表示 ii 子树内，考虑当前的连通块是否已经产生过贡献时，ii 子树中的总贡献。为了方便实现可以一产生贡献就累积到答案中。

第三问

答案为第二问的式子最后乘上一个 cntcnt 表示属于第一棵树的 ss 的数量。套用第二问的式子得到：

(1−y)nn4∑{s},∣s∣=j∏i=1jyn21−yai2\frac{(1-y)^n}{n^4} \sum_{\{s\},\left|s\right|=j} \prod_{i=1}^j \frac{yn^2}{1-y} a_i^2

用 EGF 往里面套：

F(x)=∑yn21−yi2xii!ii−2F(x) = \sum \frac{yn^2}{1-y} i^2 \frac{x^i}{i!} i^{i-2}

这里乘上的 ii−2i^{i-2} 表示前面算的是一个连通块的情况，而连通块的方案数为 ii−2i^{i-2}。

ans=ynn4n![xn]eF(x)ans = \frac{y^n}{n^4}n! [x^n]e^{F(x)}

多项式 exp 即可。

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=400005,mod=998244353;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    a=(a+mod)%mod;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}
namespace DXS{ // 多项式板子
	int rev[max_n*2],iv[max_n*2];
	int F[max_n*2],G[max_n*2],F1[max_n*2],G1[max_n*2],F2[max_n*2],G2[max_n*2];
	const int mod=998244353,_G=3,IG=332748118;

    inline void init(int n){
        for(register int i=1;i<=n*2;++i)
            iv[i]=mi(i);
    }
	inline void NTT(int *g,int n,bool op){
	    for(register int i=0;i<n;++i)
	        rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
		for(register int i=0;i<n;++i) if(i<rev[i])
			swap(g[i],g[rev[i]]);
		for(register int mid=1;mid<n;mid<<=1){
			int omega=mi(op?3:mi(3,mod-2),(mod-1)/(mid+mid));
			for(register int i=0;i<n;i+=mid+mid){
				int w=1;
				for(register int j=0;j<mid;++j,w=(w*omega)%mod){
					int x=g[i+j],y=w*g[i+j+mid]%mod;
					g[i+j]=(x+y)%mod,
					g[i+j+mid]=(x-y+mod)%mod;
				}
			}
		}
		if(!op){
			for(register int i=0;i<n;++i)
				g[i]=g[i]*iv[n]%mod;
		}
	}
	inline void Inv(int *f,int *g,int n){
	    if(n==1){
	        g[0]=iv[f[0]];
	        return;
	    }
	    Inv(f,g,n>>1);
	    for(register int i=0;i<n;++i)
	        F1[i]=f[i],G1[i]=g[i];
	    int len=(n<<1);
	    NTT(F1,len,1),NTT(G1,len,1);
	    for(register int i=0;i<len;++i)
	        F1[i]=F1[i]*G1[i]%mod*G1[i]%mod;
	    NTT(F1,len,0);
	    for(register int i=0;i<n;++i)
	        g[i]=(g[i]+g[i]-F1[i]+mod)%mod;
	    for(register int i=0;i<len;++i)
	        F1[i]=G1[i]=0;
	}
	inline void Dir(int *f,int *g,int n){
	    for(register int i=1;i<n;++i)
	        g[i-1]=f[i]*i%mod;
	    g[n-1]=0;
	}
	inline void Int(int *f,int *g,int n){
	    for(register int i=1;i<n;++i)
	        g[i]=f[i-1]*iv[i]%mod;
	    g[0]=0;
	}
	inline void Ln(int *f,int *g,int n){
	    Dir(f,F,n),Inv(f,G,n);
	    int len=n<<1;
	    NTT(F,len,1),NTT(G,len,1);
	    for(register int i=0;i<len;++i)
	        F[i]*=G[i],F[i]%=mod;
	    NTT(F,len,0),Int(F,g,len);
	    for(register int i=0;i<len;++i)
	        F[i]=G[i]=0;
	}
	inline void Exp(int *f,int *g,int n){
	    if(n==1){
	        g[0]=1;
	        return;
	    }
	    int len=n<<1;
	    Exp(f,g,n>>1),Ln(g,F2,n);
	    F2[0]=(f[0]+1-F2[0]+mod)%mod;
	    for(register int i=1;i<n;++i)
	        F2[i]=(f[i]-F2[i]+mod)%mod;
	    NTT(F2,len,1),NTT(g,len,1);
	    for(register int i=0;i<len;++i)
	        g[i]*=F2[i],g[i]%=mod;
	    NTT(g,len,0);
	    for(register int i=n;i<len;++i)
	        g[i]=F2[i]=0;
	}
}
struct graph{
   int hd[max_n],nx[max_n*2],to[max_n*2],ct;
   graph(){ct=1;}
   inline void add(int u,int v){
       nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
   }
}e;

int n,y,op;

namespace op0{ // 第一问
    set<pair<int,int> >st;
    inline void solve(){
        int cnt=n;
        for(register int i=1;i<n;++i){
            int u=read(),v=read();
            if(u>v) u^=v^=u^=v;
            st.insert(make_pair(u,v));
        }
        for(register int i=1;i<n;++i){
            int u=read(),v=read();
            if(u>v) u^=v^=u^=v;
            if(st.count(make_pair(u,v)))
                --cnt;
        }
        write(mi(y,cnt));
    }
}
namespace op1{ // 第二问
    int f[max_n],g[max_n],t;
    inline void dfs(int u,int fa){
        f[u]=1,g[u]=t;
        for(register int i=e.hd[u];i;i=e.nx[i]){
            int v=e.to[i];
            if(v==fa) continue;
            dfs(v,u);
            g[u]=(g[u]*g[v]%mod+g[u]*f[v]%mod+f[u]*g[v]%mod)%mod,
            f[u]*=(f[v]+g[v])%mod,f[u]%=mod;
        }
    }
    inline void solve(){
        if(y==1){
            write(mi(n,n-2));
            return;
        }
        t=n*y%mod*mi(1-y)%mod;
        for(register int i=1;i<n;++i){
            int u=read(),v=read();
            e.add(u,v),e.add(v,u);
        }
        dfs(1,1);
        write(g[1]*mi(1-y,n)%mod*mi(n,mod-3)%mod);
    }
}

int a[max_n*2],as[max_n*2];
int fac[max_n],inv[max_n],t;

inline void op2__solve(){ // 第三问
    if(y==1){
        write(mi(n,2*n-4));
        return;
    }
    fac[0]=inv[0]=1,t=y*n%mod*n%mod*mi(1-y)%mod;
    for(register int i=1;i<=n;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[n]=mi(fac[n]);
    for(register int i=n-1;i>=1;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    a[0]=0;
    for(register int i=1;i<=n;++i)
        a[i]=t*mi(i,i)%mod*inv[i]%mod;
    int tmp=1;
    while(tmp<=n+1) tmp<<=1;
    DXS::init(tmp);
    DXS::Exp(a,as,tmp);
    write(as[n]*fac[n]%mod*mi(1-y,n)%mod*mi(n*n%mod*n*n%mod)%mod);
}

signed main(){
	n=read(),y=read(),op=read();
	if(op==0) op0::solve();
	if(op==1) op1::solve();
	if(op==2) op2__solve();
	return 0;
}
  • 标题: Luogu5206 数树
  • 作者: Arahc
  • 创建于 : 2022-01-16 08:00:00
  • 更新于 : 2023-09-02 22:53:54
  • 链接: https://arahc.github.io/2022/01/16/【题解】Luogu5206-数树/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
Luogu5206 数树
  1. 题面
  2. 题解
    1. 第一问
    2. 第二问
    3. 第三问
  3. 代码