1868C
CF1868C Travel Plan 题解
原题 翻译 发现所有长度相同的简单路径的权值可能情况相同,且最长的简单路径长度为 \(O(\log n)\) 级别,考虑维护所有长度的简单路径在一棵树上出现的次数,每种简单路径的权值在所有树上出现的次数,相乘即使答案。 我们考虑长度为 \(x\) 的路径对答案的贡献,考虑枚举这条路径的贡献 \(k\ ......
CF1868C Travel Plan
注意到树的深度很小,所以路径长度也很小,可以先 DP 出每种路径长度的数量。 令 \(f_{i,j,0/1}\) 表示深度为 \(i\) 的满二叉树,长度为 \(j\) 的路径,一个端点不一定/一定在根结点的数量。跨越左右子树的转移就暴力枚举两侧深度。当然这里可以直接算。 但原树只是完全二叉树。观察 ......
【动态规划】【树形dp】CF1868C Travel Plan
题目描述 给定一颗 \(n\) 个节点的完全二叉树,每个点有权值 \(a_i \in [1,m]\),定义从 \(i\) 到 \(j\) 的路径的权值 \(s_{i,j}\) 为路径上的最大点权。 求所有树(\(n^m\) 种点权)的 \(\sum_{i=1}^n \sum_{j=i}^n s_{i ......