A21390.

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例

  • 输入#1

    5
    1 2
    2 3
    3 4
    4 5
    

    输出#1

    6
    
  • 输入#2

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

    输出#2

    18
    
  • 输入#3

    3
    1 2
    1 3 
    

    输出#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
首页