[Codeforces Beta Round #23 pE][DP] Tree

好久沒更新了QQ

=====================
原題連結
可以大概想到是樹形DP，但是狀態和轉移一直弄不好.....
最後是參考了大神同學的文才終於弄好的，大數模板也是直接用他的XD，畢竟我沒有手刻過大數啊QAQ
題解可以直接看他的文，講解得頗清晰。

話說這題被講義歸類在基本題的第一題，但是各種細節和大數實在是太坑了wwww

#define LL long long
#include<bits/stdc++.h>
using namespace std;
const int MOD=10000;
struct Big
{
    vector<int>*data;
    int size()const{return data->size();}
    bool operator<(const Big &a)const
    {
        if(size()!=a.size())return size()<a.size();
        for(int i=(int)size()-1;i>=0;i--)if((*data)[i]!=(*a.data)[i])return (*data)[i]<(*a.data)[i];
        return false;
    }
    void Carry()
    {
        for(int i=0;i<size();i++)if((*data)[i]>=MOD)
        {
            if(i+1==size())data->push_back(0);
            (*data)[i+1]+=(*data)[i]/MOD;
            (*data)[i]%=MOD;
        }
    }
    Big operator*(const Big &a)const
    {
        Big ans;
        ans.data->resize((int)(size()+a.size())-1,0);
        for(int i=0;i<(int)size();i++)for(int j=0;j<(int)a.size();j++)(*ans.data)[i+j]+=(*data)[i]*(*a.data)[j];
        ans.Carry();
        return ans;
    }
    void operator*=(const Big &a){(*this)=(*this)*a;}
    void operator++(){(*data)[0]++;Carry();}
    Big():data(new vector<int>()){}
    Big(const int b):data(new vector<int>()){data->push_back(b);Carry();}
    Big(const Big &a):data(new vector<int>())
    {
        data->resize(a.size());
        for(int i=0;i<a.size();i++)(*data)[i]=(*a.data)[i];
    }
    void print()
    {
        for(int i=size()-1;i>=0;i--) if(i==size()-1) printf("%d",(*data)[i]); else printf("%04d",(*data)[i]);
    }
};
const int maxn=700+5;
Big d[maxn][3]; // d[now][0]:ans,d[now][1]: if every tree edges gone, d[now][2]: at least one edge stay
vector<int> G[maxn];
Big getmax(const Big& a,const Big& b) {return a<b?b:a;}
bool cmp(pair<Big,Big>& a,pair<Big,Big>& b) { return a.first*b.second<a.second*b.first; }
void dfs(int now,int fa)
{
    vector<pair<Big,Big> > vpii;
    vector<Big> pre,suf;
    d[now][0]=d[now][1]=d[now][2]=Big(1);
    for(const int& to:G[now]) if(to!=fa)
    {
        dfs(to,now);
        d[now][1]*=d[to][0]; 
        vpii.push_back(make_pair(d[to][1],d[to][0]));
    }
    // d[now][1] over
    sort(vpii.begin(),vpii.end(),cmp);
    suf.resize(vpii.size());pre.resize(vpii.size());
    Big tmp=Big(1);
    for(int i=vpii.size()-1;i>=0;i--)
    {
        tmp*=vpii[i].first;
        suf[i]=tmp;
    }
    tmp=Big(1);
    for(int i=0;i<vpii.size();i++)
    {
        tmp*=vpii[i].second;
        pre[i]=tmp;
    }
    LL sz=(int)vpii.size()+2;
    d[now][0]=getmax(d[now][0],(vpii.size()?suf[0]:1)*Big(sz-1));
    d[now][2]=getmax(d[now][2],(vpii.size()?suf[0]:1)*Big(sz));
    for(int i=0;i<vpii.size();i++) // take edges off
    {
        sz--;
        d[now][0]=getmax(d[now][0],pre[i]*(i+1<vpii.size()?suf[i+1]:Big(1))*Big(sz-1));
        d[now][2]=getmax(d[now][2],pre[i]*(i+1<vpii.size()?suf[i+1]:Big(1))*Big(sz));
    }
    // d[now][2] over
    pre.resize(G[now].size());suf.resize(G[now].size());
    tmp=Big(1);
    for(int i=0;i<G[now].size();i++) if(G[now][i]!=fa) {tmp*=d[G[now][i]][0];pre[i]=tmp;} else pre[i]=tmp;
    tmp=Big(1);
    for(int i=G[now].size()-1;i>=0;i--) if(G[now][i]!=fa) {tmp*=d[G[now][i]][0];suf[i]=tmp;} else suf[i]=tmp;
    for(int i=0;i<G[now].size();i++) if(G[now][i]!=fa) d[now][0]=getmax(d[now][0],(i>=1?pre[i-1]:Big(1))*(i+1<G[now].size()?suf[i+1]:Big(1))*d[G[now][i]][2]);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0,a,b;i<n-1;i++)
    {
        scanf("%d%d",&a,&b);a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(0,-1);
    d[0][0].print();puts("");
}