2016年1月29日 星期五

[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;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原