P12050 三叶虫树

此题由 [QOJ 6350](https://qoj.ac/problem/6350) 加强得到。 题目背景和题意无关，可以跳过 斜二进制看上去没什么用。但是不屈的三叶虫很快发现了它的优秀性质。 不屈的三叶虫提出了一种叫三叶虫树的结构：一棵三叶虫树维护一个长度为 $2^n-1$ 的序列，其中 $n\ge 1$。 三叶虫树的根管辖整个区间，根的左子树是区间的前 $2^{n-1}-1$ 个元素构建的三叶虫树，右子树是区间的接下来 $2^{n-1}-1$ 个元素构建的三叶虫树。注意最后一个元素不属于任何一棵子树，它是特别的——也正因如此，我们可以将一棵三叶虫树的根编号为它最后一个元素的下标。 不难发现，如果假设整个序列从一开始编号并把三叶虫树的每个节点的斜二进制写出，那么根管辖的斜二进制区间将是 $(0,100\cdots0]$，左子树的管辖区间是 $ (0,10\cdots0]$，右子树的管辖区间是 $(10\cdots0,20\cdots0]$。我们不难证明，一个点 $i$ 为根的子树的管辖区间的左端点 $j=i-{skew\_lowbit}(i)$，其中 ${skew\_lowbit}(i)$ 表示 $i$ 在斜二进制下的最低有效位。 考虑将 $n$ 进行斜二进制分解并用一系列三叶虫树来维护序列，可以实现一些简单的操作。

为了建立伟大的三叶虫帝国，不屈的三叶虫给了你一棵大小为 $n$ 的边带正权的树 $T$，对于每个 $i=1...\lfloor\frac n2\rfloor$ 求完全图 $G$ 的大小为 $i$ 的最大权匹配，其中在 $G$ 中连接 $i$ 和 $j$ 的边权与 $T$ 中 $i$ 到 $j$ 的距离相等。

第一行一个正整数 $n$。 接下来 $n-1$ 行，每行三个正整数 $u,v,w$，表示树上一条边。

一行 $\lfloor\frac n2\rfloor$ 个整数，表示答案。

样例中，对于匹配大小分别为 $1,2,3$ 的情况，最优的方案分别为 $(1,2)$，$(1,5),(2,6)$，$(1,7),(2,5),(3,6)$。请注意这并非唯一的方案。 对于全部的数据，$1\le n,w\le 10^6$。 |子任务编号|分值|$n\le$|特殊限制| |:-:|:-:|:-:|:-:| |$1$|$5$|$7$|-| |$2$|$5$|$80$|$w=1$| |$3$|$20$|$10^3$|-| |$4$|$20$|$10^4$|-| |$5$|$10$|$10^5$|度数为 $1$ 的点至多有 $25$ 个| |$6$|$5$|$10^5$|度数为 $1$ 的点至少有 $n-1$ 个| |$7$|$15$|$10^5$|-| |$8$|$20$|$10^6$|-|