树上信息表示

欧拉序

树的一条欧拉回路上的点的序列。

欧拉序上的区间 $\rm mindep$ 是 $\rm lca$ ，从浅往深走加左括号，从深往浅走加右括号，那么区间括号匹配后剩下的部分就是这条路径的信息。

后者被称为括号序。

欧拉序看作边的序列，那么第一种欧拉序是每条边换成上点，第二种（括号序）是每条边换成下点。

题

插叶子，查子树直径。

放在括号序上就是单点插入，求区间最大子段（特殊定义）和。

单点插入可以时光倒流变成单点修改，形如 $\text{)))))((((((}$ 这种东西的最大子段显然只需要维护左边的最大 $)))$ ，最大 $)))(((($ ，右边的最大 $((($ ，最大 $)))((((($ ，易于合并。

P2056 [ZJOI2007] 捉迷藏

也可以利用括号序做。

这就是树上欧拉回路的优势：任意一个连通块都可以用括号序表示。

prufer 序列：树的组合表示

是无根树的表示方法，与无根树形成双射。

定义：每次在所有叶子里找到编号最大的，删掉，并将相邻点加入 prufer 序列，在 $n=2$ 时停止。

显然一棵树可以映射到一个序列。

考虑序列到树的映射，考虑 prufer 中没出现的点，这是初始的叶子集合，将其中最大的和它的父亲（ $a_1$ ）合并，归纳。

每个点的出现次数是度数减一。

题

给出每个点的度数，问树的个数。

多重组合数即可。

题

左边 $n$ 个点右边 $m$ 个点的完全二分图，求出生成树个数。

最后一次肯定是左右只剩一个点，所以一定出现了 $n-1$ 次右边的点， $m-1$ 次左边的点。

考虑这两边子序列我们都确定了，将其归并起来的方案数。

左边的叶子在序列 $b$ 没出现，右边的叶子在序列 $a$ 中没出现。

你发现我们可以自然确定出没出现的最大的叶子是左边还是右边，所以我们可以确定第一个位置。

所以顺序已经确定，答案是 $n^{m-1}m^{n-1}$ 。

UOJ#176. 新年的繁荣

零点的钟声敲响，猴年终于到来啦~

在这新年的第一天，猴族首领猴腮雷打算重新规划一下猴族领地的交通。

猴族领地中有 $n$ 个城市，其中第 $i$ 座城市的繁荣度为 $a_i$ 。猴族领地中任意两个城市之间都可以修建双向道路，在第 $i$ 座城市和第 $j$ 座城市之间修建道路可以给新的一年带来 $a_i \mathbin{\mathrm{and}} a_j$ 的繁荣度。其中 $\mathbin{\mathrm{and}}$ 表示按位与运算，例如：

$2 \mathbin{\mathrm{and}} 3 = 2$

$1 \mathbin{\mathrm{and}} 0 = 0$

$1 \mathbin{\mathrm{and}} 1 = 1$

为了彰显自己的功绩，猴族首领猴腮雷决定修建若干条道路，使得任意两个城市之间都可以只通过他新修建的道路直接或者间接到达。为了发扬节约精神，他决定修建恰好 $n-1$ 条道路。一个修建方案的繁荣度是所有要修建的道路带来的繁荣程度之和。

作为一个英明的首领，猴腮雷决定在所有可行的方案中选择繁荣度最大的方案，现在他想要知道他选择的方案的繁荣度，但因为他日理万机，没有时间来想这种简单的小问题，于是他就让你来帮忙啦。

$n\le 10^5,V<2^{18}$ 。

这个题比较牛，

考虑 boruvka，按位确定每个连通块向外的最大边。

我们确实不会求这个，但是我们会求内部的最大边（ $n\log V$ 按位确定，扔掉应该扔的），还会求内部匹配全局的最大边（形如 $\text{1**1***1}$ 的需求，高位前缀和即可），且两种都能在线且计数，我们减一下就能知道内部匹配外部有没有这种边。

但是我们还需要确定匹配到了哪个人，还是有点困难。

有一个简单到极致的 kruskal 做法，首先相同点权先缩点，从大到小枚举边权，枚举到一个点时从所有超集继承过来，遇到不同的连通块就合并。

最小生成树的01原理：LOJ#6631. 「EC Final 2018」异国情调的……古城 / Exotic … Ancient City

$01$ 原理是每个 $\ge k$ 的有效边贡献 $1$ ，也就是 $n-(<k$ 的联通块数 $)$ 。

可以用有向图来替代两边点数相等的无向二分图。