[Codeforces Beta Round #23]E. Tree

首先可以知道一個性質，就是刪完邊之後不存在一條長度$>2$的路徑

證明：
可以把路徑中間那條邊拔掉，會變成兩棵樹$a$、$b$，此時有$a.size()\geq 2$且$b.size()\geq 2$，因此拆邊後變成$a.size()*b.size()\geq a.size()+b.size()$

因此，我們可以對每顆子樹(根節點$u$)構造$DP_{0}[u]$、$DP_{1}[u]$和$DP_{2}[u]$，分別代表這顆子樹在某些限制條件下，刪邊之後，可以得到最高的分數
限制如下：
$DP_{0}[u]$：所有連接$u$的邊都必須刪除
$DP_{1}[u]$：如果$u$和子節點$v$之間的邊沒有刪除，那麼$v$的其他邊都要刪除，且$u$的$size$要當作$2$(用來方便計算$DP_{2}$)
$DP_{2}[u]$：沒有限制，所以本題答案為$DP_{2}[0]$(如果根節點為$0$的話)

轉移式如下($v_{i}$代表$u$的子節點，$sz$代表子節點數量)：
$DP_{0}[u]$：$\sum_{all\ i}DP_{2}[v_{i}]$
$DP_{1}[u]$：枚舉要連邊的子節點集合$s$，$\max_{all\ s}((\prod_{all\ i}i\in s?DP_{0}[v_{i}]:DP_{2}[v_{i}])*(s.size()+2))$，可以用貪心法將子樹依據$\frac{DP_{0}[v_{i}]}{DP_{1}[v_{i}]}$排序，然後取$\max_{k=0}^{sz}(\prod_{i=1}^{k}DP_{0}[v_{i}])*(\prod_{i=k+1}^{sz}DP_{1}[v_{i}])*(k+2)$，預處理前綴後綴乘積可做到$O(sz\log sz)$，注意這裡要將$u$的$size$當作$2$，也就是上述式子$+2$的由來
$DP_{2}[u]$：$max\{DP_{0}[u],u的size是1時的DP_{1}[u],\max_{all\ i}\frac{(\prod_{all\ j}DP_{2}[v_{j}])*DP_{1}[v_{i}]}{DP_{2}[v_{i}]}\}$

注意，本題需要大數運算，但為了邏輯清楚，以下先給出用$long\ long$實作的code，本code無法AC！

用大數運算實作可AC的code在這裡

時間複雜度：$O(N^{2}\log N)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
void getmax(LL &a,const LL &b){if(b>a)a=b;}
int N;
LL DP[700][3];
vector<int>ET[700];
struct Type
{
    LL yes,no;
    Type(){}
    Type(const LL &_yes,const LL &_no):yes(_yes),no(_no){}
    bool operator<(const Type &t)const{return yes*t.no<no*t.yes;}
};
LL Dfs(const int u,const int fa,const int dep)
{
    LL &ans=DP[u][dep];
    if(ans!=-1LL)return ans;
    if(true)
    {
        ans=1LL;
        for(const int nxt:ET[u])if(nxt!=fa)ans*=Dfs(nxt,u,2);
    }
    if(dep==0)return ans;
    if(true)
    {
        vector<Type>chinfo;
        for(const int nxt:ET[u])if(nxt!=fa)chinfo.push_back(Type(Dfs(nxt,u,0),Dfs(nxt,u,2)));
        sort(chinfo.begin(),chinfo.end());
        LL ta=1LL,sz=(dep==1?2LL:1LL)+(LL)chinfo.size();
        for(const auto &v:chinfo)ta*=v.yes;
        ans=sz*ta;
        for(const auto &v:chinfo)
        {
            (ta/=v.yes)*=v.no,sz--;
            getmax(ans,sz*ta);
        }
    }
    if(dep==1)return ans;
    if(true)
    {
        LL ta=1LL;
        for(const int nxt:ET[u])if(nxt!=fa)ta*=Dfs(nxt,u,2);
        for(const int nxt:ET[u])if(nxt!=fa)
        {
            getmax(ans,ta/Dfs(nxt,u,2)*Dfs(nxt,u,1));
        }
    }
    assert(dep==2);
//    printf("ans=%lld\n",ans);
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=0,a,b;i<N-1;i++)
        {
            scanf("%d%d",&a,&b),a--,b--;
            ET[a].push_back(b),ET[b].push_back(a);
        }
        LL ans=Dfs(0,-1,2);
        printf("%I64d\n",ans);
    }
    return 0;
}