通用cms网站,湖南省博物馆网站建设,合肥手机网站建设,php网站开发案例论文Prufer 序列 定义与建立 Prufer 序列可以将一个带标号 \(n\) 个结点的树用 \([1,n]\) 中的 \(n-2\) 个整数表示。一个无向带标号生成树与数列之间的双射。 对于一棵树#xff0c;每次我们选择它编号最小的叶子结点#xff0c;删除它并记录下与它相连的节点的编号#xff0c;… Prufer 序列 定义与建立 Prufer 序列可以将一个带标号 \(n\) 个结点的树用 \([1,n]\) 中的 \(n-2\) 个整数表示。一个无向带标号生成树与数列之间的双射。 对于一棵树每次我们选择它编号最小的叶子结点删除它并记录下与它相连的节点的编号那么最终记录下的 \(n-2\) 个数就组成了这棵树的 Prufer 序列。 显然用这个东西维护树的结构感觉非常不好这个东西主要用来数数用的。 对树建立 Prufer 序列 按照定义直接建立那么每次从堆中取出最小的数删去它并记录。 这样可以得到一个 \(\mathcal{O(n\log n)}\) 的做法但是显然这不够优美我们需要一个 \(\mathcal{O(n)}\) 的解法。 我们发现剩余的叶子结点数量是递减的每次删除要么少一个要么少一个又多一个。 从小到大枚举编号 \(p\)如果是叶子结点将和它们相邻的点放入 Prufer 序列中。考虑这个叶子结点带来的新叶子结点 如果和它相邻的点编号 \(pp\) 或者 \(p\) 没有变成叶子结点那么不用管它会在之后被枚举到。但是如果 \(pp\)它在时候不会被枚举到了。但是发现删除之前当前最小的叶子结点是 \(p\)所以删后 \(p\) 必然是最小的叶子所以可以直接继续删除 \(p\)。 for(int i1,x;in;i) xrd(),add(i,x),add(x,i),ind[i],ind[x];
// [1,n-1] 的父亲序列
for(int i1;in;i) if(ind[i]1) exist[i]true;
for(int i1,p;in;i)
{if(!exist[i]) continue;pi;while(pi){used[p]true;for(int jhea[p];j;jnex[j])if(!used[ver[j]]) { pver[j]; break; }if(ind[p]1) break;ind[p]--,pru[cnt]p;if(ind[p]1) exist[p]true;if(ind[p]!1 || pi) break;}if(ind[p]1) exist[p]true;
}
assert(cntn-2);
for(int i1;icnt;i) ret^1ll*i*pru[i];
printf(%lld\n,ret); 用 Prufer 还原无根树 发现 Prufer 序列中的每个数的出现次数就是原树中每个点的度数 \(-1\)可以每次连一个叶子结点重构。 方法类似一个暴力的做法是每次选出最小的当前的叶子结点将它与 Prufer 序列最前面的元素相连这样复杂度是 \(\mathcal{O(n\log n)}\) 的。 发现叶子结点编号递增设删去的叶子结点为 \(p\)和它相邻的是 \(p\)。当加完 \(p\) 后 \(p\) 的度数变为 \(1\) 并且 \(pp\)那么它下一次一定被选择直接继续连边即可。 for(int i1;in-2;i) pru[i]rd(),ind[pru[i]];
for(int i1;in;i) if(!ind[i]) exist[i]true;
int pos1;
for(int i1,p;in;i)
{if(!exist[i]) continue;pi;while(pi){if(posn-1) { fa[p]n; break; }fa[p]pru[pos],ppru[pos],ind[p]--,pos;if(posn) break;if(ind[p] || pi) break;}if(!ind[p]) exist[p]true;
}
for(int i1;in;i) ret^1ll*i*fa[i];
printf(%lld\n,ret); 主要性质 Prufer 序列与无根树一一对应(好像比较显然) 度数为 \(d_i\) 的点在 Prufer 序列中出现 \(d_i-1\) 次(上面还用到了这个结论) 【根据度数求方案】对于给定每个点度数为 \(d_i\) 的无根树方案数为 \[\dfrac{(n-2)!}{\prod_{i1}^{n}(d_i-1)!} \]证明Prufer 序列长度为 \(n-2\)每个数出现次数为 \(d_i-1\)根据组合意义直接计算全排列即可。 【根据连通块数量与大小求方案】一个 \(n\) 个点 \(m\) 条边的带标号无向图有 \(k\) 个连通块每个连通块大小为 \(s_i\)需要增加 \(k-1\) 条边使得整个图联通方案数为(但是当 \(k1\) 时需要特判) \[n^{k-2}\cdot\prod_{i1}^{k}s_i \]证明见 OI-wiki
