#P18536. Idola-Tree
Idola-Tree
Idola-Tree
偶像组合 Oshikoshi 想请你为新专辑封面设计一件数学艺术品。封面是一棵树:有 位偶像,以及 条曲线,每条曲线双向连接一对不同的偶像。
简单路径是由至少两位互不相同的偶像组成的序列,相邻偶像之间都有一条曲线。树中任意两个不同顶点之间恰有一条简单路径。从 到 与从 到 算作同一条路径,因此共有 条不同的简单路径。
Oshikoshi 给出如下定义:
- 每条曲线的长度都是正整数。
- 整棵树的“墨水费用”等于全部 条曲线的长度之和。
- 一条简单路径的长度等于这条路径上所有曲线长度之和。
- 路径的长度平方是先把路径上各条曲线的长度相加,再取平方。例如两条曲线长度分别为 ,应计算 ,而不是 。
- 树的“戏剧性”是全部 条不同简单路径的长度平方之和。
树的形状已经确定,即哪些偶像之间由曲线直接连接已确定;每条曲线的长度仍待决定。
给定整数 ,考虑所有使墨水费用恰好等于 的正整数边长分配。令其中最小的戏剧性为 。
现在给你整数 ,请计算
上下界均包含在求和范围内,每一个 可以独立选择自己的最优边长分配。
输入格式
第一行一个整数 ,表示测试用例数。随后依次给出 个测试用例。
每个测试用例第一行两个整数 。接下来 行,每行两个 到 之间的整数,表示一条曲线直接连接的两位偶像。顶点编号为 到 。给出的无向图是一棵树。
- ;
- ;
- 。
原题没有额外给出同一输入文件内 或 的总和限制。
输出格式
每个测试用例输出一行,一个整数,表示该测试用例的答案。
原样例
2
4 3
1 4
1 3
2 1
4 4
1 4
1 3
2 1
3375
25327
样例说明
两例使用同一棵树。
- 时,三条边只能全部取 ,于是 。
- 时,一种最优分配是把连接偶像 与 的边长取为 ,其余两条边长为 。这时 。
所以第一例是 ,第二例是 。