问题 1
问题描述
树上各点均有对应的颜色，现给定节点 u，判断以 u 为根的子树中已存在的颜色所对应的节点数是否两两相同。
问题解决
- 用 \(c_u\) 表示节点 u 所对应的颜色，\(sz_u\) 表示以 u 为根的子树的大小，\(cnum_i\) 表示颜色 i 在当前子树出现的次数，\(numc_i\) 表示在当前子树中出现次数为 i 的颜色有多少种。故若 \(cnum[c_u]\times numc[cnum[c_u]]=sz[u]\)，则以 u 为根的子树中已存在的颜色所对应的节点数两两相同。
- 可用 dsu on tree 以 \(\mathcal O(n\log n)\) 的时间复杂度处理出所有节点的答
问题 2
问题描述
设 \(n\) 为 任意正奇数，求 \(n\) 个两两互异的 \(n\) 位数，且满足他们的组成数字的可重集合均相同。如 \(n=3\) 时，169、196、961 符合答案。
问题解决
- 重点在于发现完全平方数100的特殊性——任何完全平方数的 \(100\) 倍仍为完全平方数。故 \(n+2\) 的答案可由 \(n\) 的答案生成 \(n\) 个数。
- 剩下的两个答案形式满足 \(9\dots6\dots1\) 与 \(1\dots6\dots9\)，其中，\(\dots\) 表示 \(\frac{n-3}{2}\) 个 \(0\)。
- 时间复杂度位 \(\mathcal O(n^2)\)。