「SOL」The Hanged Man(HDU)-有解無憂

看到課程標題是 “DP優化”，以為就是斜率優化、單調性之類的……
結果來了些什么奇妙操作

# 題面

給定一棵 \(n\) 個點的樹和整數 \(m\)，每個點有兩類權值 \(a_i,b_i\)，

對于每個 \(h=1\sim m\)，求樹上的一個獨立集 \(S\)，使得 \(\sum\limits_{i\in S}a_i\le h\)，且 \(\sum\limits_{i\in S}b_i\) 最大，輸出滿足上述條件的 \(S\) 的數量，

資料規模：\(n\le50,m\le5000,1\le a_i\le m,b_i\le 10^6\)，

# 決議

題面就描述了一個背包問題，另外有獨立集的限制，

如果在原樹上直接背包，需要背包合并（由于物品大小并非 \(1\)，雖然兩個點只會在 LCA 處產生貢獻，但是合并的復雜度仍然是 \(\mathcal{O}(m^2)\) 的），復雜度只能是 \(\mathcal{O}(nm^2)\)，無法再優化，

話不多說，我們直接來看看怎么用神仙操作來做這道題，

首先我們建出原樹的點分樹，點分樹有兩個（重要的）性質，其中一條我們非常熟悉：

樹高是 \(\mathcal{O}(\log n)\)，

另外一條非常顯然但是不常用（至少我沒見過哪道題用）：

原樹上與 \(u\) 相鄰的點在點分樹上只可能是 \(\mathbf{u}\) 的祖先 和 \(u\) 的后繼，

怎么利用這兩點來解題？我們考慮按照點分樹的 DFS 序 依次決策每個節點是否在獨立集中，

這樣的話，當我們決策 \(u\) 時，就不需要考慮 \(u\) 的后繼是否選入獨立集，而只需要考慮 \(\mathbf{u}\) 的祖先 有哪些被選入了獨立集中 —— \(u\) 的祖先不多，只有 \(\mathcal{O}(\log n)\) 個，于是可以狀壓：\(f_{u,s,i}\) 表示的狀態為「已經決策了 \(u\)，從根到 \(u\) 的鏈上被選入獨立集的點是 \(s\)（壓縮狀態），且當前背包中裝了總重為 \(i\) 的物品」，需要維護對應的物品價值最大值以及方案數，

那么 \(s\) 的范圍是 \(\mathcal{O}(2^{\log n})=\mathcal{O}(n)\) 的，\(f_{u,s,i}\) 的狀態數是 \(\mathcal{O}(n^2m)\) 的，由于是 0-1 背包，可以 \(\mathcal{O}(1)\) 轉移，總的復雜度也是 \(\mathcal{O}(n^2m)\) 的，

下面關于一些細節簡單說一下：

知道了祖先的選定狀態 \(s\)，如何判斷 \(u\) 是否能加入當前的獨立集中？為了保持復雜度必須 \(\mathcal{O}(1)\) 判斷：
- 維護壓縮狀態 lnk[u] 表示當前點分樹的祖先中，哪些是原樹上與 \(u\) 相連的節點，
- 判斷只需要判斷 lnk[u] 和 \(s\) 是否有交；
- 維護只需要在 DFS 進入點 \(u\) 時列舉原樹上與 \(u\) 相鄰的點 \(v\)，更新 lnk[v]，DFS 退出點 \(u\) 時在 lnk 中撤銷 \(u\) 的資訊即可，
\(f_{u,s,i}\) 中壓縮狀態 \(s\) 的維護：記 \(u\) 在 DFS 序上的前驅為 \(v\)，我們需要從 \(f_v\) 轉移到 \(f_u\)，
- 只需要深度小于 \(dep_u\) 的祖先；
- 就需要把 \(f_{v,s,i}\) 的 \(s\) 中深度大于等于 \(dep_u\) 的部分刪去；
- 具體的，在 DFS 退出點 \(u\) 時，對每個 \(s\ge 2^{dep_u}\)，將 \(f_{u,s,i}\) 貢獻到 \(f_{u,s-2^{dep_u},i}\)；
- 這樣的效果就是遞回到當前層時，有用的 \(s\) 的位數不超過 \(dep_v-1\)，

大概是一個不錯的處理獨立集的方法……

# 源代碼

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int rin(int &r){
    int b=1,c=getchar();r=0;
    while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
    while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
    return r*=b;
}
const int N=55,M=5005;
#define con(type) const type &

struct Data{
    int key;long long cnt;
    friend void maxc(Data &a,con(Data)b){
        if(a.key<b.key) a=b;
        else if(a.key==b.key) a.cnt+=b.cnt;
    }
    Data operator +(con(int)d)const{return (Data){key+d,cnt};}
}f[2][64][M];
struct Graph{
    int head[N],to[N<<1],nxt[N<<1],ncnt;
    void init(con(int)sz){for(int i=1;i<=sz;i++)head[i]=0;ncnt=0;}
    void addEdge(con(int)u,con(int)v,con(bool)typ=true){
        ncnt++;
        to[ncnt]=v,nxt[ncnt]=head[u],head[u]=ncnt;
        if(typ) ncnt++,to[ncnt]=u,nxt[ncnt]=head[v],head[v]=ncnt;
    }
    inline int operator [](con(int)u){return head[u];}
}gr;

int ncas,n,m,r_wei,r_root,r_tot,bagsiz,ndfn;
int ara[N],arb[N],nxtto[N];
bool ban[N];

int toggleSize(con(int)u,con(int)fa){
    int sizu=1;
    for(int it=gr[u];it;it=gr.nxt[it])
        if(gr.to[it]!=fa && !ban[gr.to[it]])
            sizu+=toggleSize(gr.to[it],u);
    return sizu;
}
int findCenter(con(int)u,con(int)fa){
    int sizu=1,mxv=0;
    for(int it=gr[u];it;it=gr.nxt[it]){
        int v=gr.to[it],sizv;
        if(v==fa || ban[v]) continue;
        sizv=findCenter(v,u);
        sizu+=sizv,mxv=max(mxv,sizv);
    }
    mxv=max(mxv,r_tot-sizu);
    if(r_wei>mxv) r_wei=mxv,r_root=u;
    return sizu;
}
void dacDFS(con(int)u,con(int)dep){
    // # Marks
    for(int it=gr[u];it;it=gr.nxt[it]) nxtto[gr.to[it]]|=1<<dep;
    ban[u]=true;
    // # DP
    int I=(++ndfn)&1;
    for(int s=0,ss=1<<(dep+1);s<ss;s++)
        for(int i=0,ii=m;i<=ii;i++)
            f[I][s][i].key=-1,f[I][s][i].cnt=0;
    if(dep){
        for(int s=0,ss=1<<dep;s<ss;s++)
            for(int i=0;i<=bagsiz;i++)
                f[I][s][i]=f[!I][s][i];
        int ii=min(bagsiz,m-ara[u]);
        for(int s=0,ss=1<<dep;s<ss;s++){
            if(nxtto[u]&s) continue;
            for(int i=0;i<=ii;i++)
                if(~f[!I][s][i].key)
                    maxc(f[I][s|(1<<dep)][i+ara[u]],f[!I][s][i]+arb[u]);
        }
    }
    else{
        f[I][0][0].key=0,f[I][0][0].cnt=1;
        f[I][1][ara[u]].key=arb[u],f[I][1][ara[u]].cnt=1;
    }
    bagsiz=min(m,bagsiz+ara[u]);
    // # Transport
    for(int it=gr[u];it;it=gr.nxt[it]){
        int v=gr.to[it],sizv;
        if(ban[v]) continue;
        sizv=toggleSize(v,0);
        r_tot=sizv,r_wei=n+1,findCenter(v,0);
        int rtv=r_root;
        // printf("%d -> %d\n",u,v);
        dacDFS(rtv,dep+1);
    }
    // # Roll-back
    for(int it=gr[u];it;it=gr.nxt[it]) nxtto[gr.to[it]]^=1<<dep;
    ban[u]=false;
    // # Toggle-DP
    I=ndfn&1;
    for(int s=1<<dep,ss=1<<(dep+1);s<ss;s++)
        for(int i=0;i<=bagsiz;i++)
            maxc(f[I][s^(1<<dep)][i],f[I][s][i]);
}
int main(){
    rin(ncas);
    for(int cas=1;cas<=ncas;cas++){
        rin(n),rin(m);
        // # Clear
        gr.init(n);
        bagsiz=ndfn=0;
        // # Read & Init-build
        for(int i=1;i<=n;i++) rin(ara[i]),rin(arb[i]);
        for(int i=1,u,v;i<n;i++) gr.addEdge(rin(u),rin(v));
        // # Calculate
        r_tot=n,r_wei=n+1,findCenter(1,0);
        int rt=r_root;
        dacDFS(rt,0);
        // # Print
        printf("Case %d:\n",cas);
        int I=ndfn&1;
        for(int i=1;i<=m;i++) printf("%lld%c",f[I][0][i].cnt,i==m?'\n':' ');
    }
    return 0;
}

THE END

Thanks for reading!

誰留下烽火連天照夜的勾劃
又是誰在傳說中尋他
千年后揮兵破陣不過一剎那
血雨腥風吻過了傷疤

——《山河令》By 忘川風華錄 / 星塵

> Link 山河令-網易云

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/265821.html

標籤：其他

上一篇：學編程難，但努力不一定會成功，幾點建議給想要把編程學好的人

下一篇：現代軟體工程作業第一周博客作業（王建民老師）