CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest7 [2021/07/27 20:21]
王智彪
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest7 [2021/07/30 17:23] (当前版本)
lgwza [补题情况]
@@ 行 7: / 行 7: @@
 |  B  |  2  |  0  |  2  |
 |  C  |  2  |  0  |  1  |
-|  D  |  0  |  0  |  0  |
+|  D  |  2  |  1  |  0  |
 |  E  |  2  |  0  |  1  |
 |  F  |  2  |  0  |  2  |
 |  G  |  2  |  0  |  2  |
-|  H  |  0  |  0  |  0  |
+|  H  |  0  |  1  |  2  |
 |  I  |  2  |  0  |  2  |
 |  J  |  2  |  0  |  2  |
 ====== 题解 ======
+===== D. Rebuild Tree =====
+==== 题意 ====
+给定一棵树，要求删除 $k$ 条边再补上 $k$ 条边，使得新图仍然是一棵树，问方案数。
+==== 题解 ====
+首先删除 $k$ 条边得到 $k+1$ 个连通块，设第 $i$ 个连通块有 $s_i$ 个点。
+固定 $(s_1,s_2\cdots s_{k+1})$，将每个连通块缩点后构造 $\text{prufer}$ 序列。设第 $i$ 个连通块在新图中得度数为 $d_i$，知每个生成树的贡献为
+$$
+\prod_{i=1}^{k+1}s_i^{d_i}
+$$
+设 $p_i$ 表示第 $i$ 个连通块在 $\text{prufer}$ 序列中出现的次数，根据 $\text{prufer}$ 序列性质，知 $d_i=p_i+1$，于是有
+$$
+\prod_{i=1}^{k+1}s_i^{d_i}=
+\left(\prod_{i=1}^{k+1}s_i\right)\left(\prod_{i=1}^{k+1}s_i^{p_i}\right)
+$$
+考虑 $\prod_{i=1}^{k+1}s_i^{p_i}$ 在 $\text{prufer}$ 序列中的实际意义。
+不难发现设 $\text{prufer}$ 序列的权值为每个元素 $a_i$ 按权值 $s_{a_i}$ 相乘之积，则所有 $\prod_{i=1}^{k+1}s_i^{p_i}$ 之和等价于所有 $\text{prufer}$ 序列的权值之和。
+不难发现，所有 $\text{prufer}$ 序列的权值之和(固定其他位置，枚举单个位置的变化)等于
+$$
+\left(\sum_{i=1}^{k+1} s_i\right)^{k-1}=n^{k-1}
+$$
+于是对固定 $(s_1,s_2\cdots s_{k+1})$，总贡献为
+$$
+\left(\prod_{i=1}^{k+1}s_i\right)\sum_{Tree(k+1)}\left(\prod_{i=1}^{k+1}s_i^{p_i}\right)=\left(\prod_{i=1}^{k+1}s_i\right)\left(\sum_{i=1}^{k+1} s_i\right)^{k-1}=\left(\prod_{i=1}^{k+1}s_i\right)n^{k-1}
+$$
+接下来考虑 $(s_1,s_2\cdots s_{k+1})$ 不固定时产生的总贡献。
+不难发现 $\prod_{i=1}^{k+1}s_i$ 等于连通块的大小之积，这可以转化为在每个连通块中选一个点的方案数。
+于是设 $\text{dp}(u,k,0/1)$ 表示以 $u$ 为子树已经割 $k$ 条边，$0/1$ 表示 $u$ 所在的连通块是否已经选择代表节点的方案数。
+进行树形 $\text{dp}$ 转移，枚举是否割断 $u$ 与 $v\in \text{son}(u)$ 的连边的贡献，注意如果 $v$ 所在的连通块没有代表节点，则 $u\to v$ 一定不可割。
+时间复杂度 $O(nk)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e4+5,MAXK=105,mod=998244353;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int quick_pow(int a,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*a%mod;
+		a=1LL*a*a%mod;
+		k>>=1;
+	}
+	return ans;
+}
+void add(int &x,LL y){
+	x=(x+y)%mod;
+}
+int sz[MAXN],dp[MAXN][MAXK][2],temp[MAXK][2];
+void dfs(int u,int fa){
+	sz[u]=1;
+	dp[u][0][0]=dp[u][0][1]=1;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs(v,u);
+		_for(j,0,min(sz[u]+sz[v],MAXK))
+		temp[j][0]=temp[j][1]=0;
+		_for(j,0,min(sz[u],MAXK))_for(k,0,min(sz[v],MAXK)){
+			if(j+k<MAXK){
+				add(temp[j+k][0],1LL*dp[u][j][0]*dp[v][k][0]);
+				add(temp[j+k][1],1LL*dp[u][j][0]*dp[v][k][1]+1LL*dp[u][j][1]*dp[v][k][0]);
+			}
+			if(j+k+1<MAXK){
+				add(temp[j+k+1][0],1LL*dp[u][j][0]*dp[v][k][1]);
+				add(temp[j+k+1][1],1LL*dp[u][j][1]*dp[v][k][1]);
+			}
+		}
+		_for(j,0,min(sz[u]+sz[v],MAXK)){
+			dp[u][j][0]=temp[j][0];
+			dp[u][j][1]=temp[j][1];
+		}
+		sz[u]+=sz[v];
+	}
+}
+int main(){
+	int n=read_int(),k=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	dfs(1,0);
+	enter(1LL*quick_pow(n,k-1)*dp[1][k][1]%mod);
+	return 0;
+}
+</code>
+</hidden>
 ===== G. Product =====

CVBB ACM Team

用户工具

站点工具

页面工具