#P1411. 树

    ID: 455 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp树形结构福建省历届夏令营

题目背景

L 发明了一种与树有关的游戏。

题目描述

他从树中删除任意数量(可以为 00)的边,计算删除后所有连通块大小的乘积,L 将得到这么多的分数。

你的任务就是对于一颗给定的树,求出 L 能得到的最大分数。

输入格式

第一行一个整数 nn,表示树的节点个数。

接下来 (n1)(n-1) 行,每行两个整数 u,vu, v,代表存在一条连接 u,vu, v 的边。

输出格式

输出一行一个整数,表示 L 能得到的最大分数。

5
1 2
2 3
3 4
4 5
6
8
1 2
1 3
2 4
2 5
3 6
3 7
6 8
18
3
1 2
1 3 
3 

提示

数据规模与约定

  • 对于 10%10\% 的数据,保证 n5n \leq 5
  • 对于 30%30\% 的数据,保证 n100n \leq 100
  • 另有 30%30\% 的数据,保证给出的树是一条链。
  • 对于 100%100\% 的数据,保证 1n7001 \leq n \leq 7001u,vn1 \leq u, v \leq n