免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

題意：
一棵結(jié)點(diǎn)帶權(quán)樹，大小(結(jié)點(diǎn)數(shù))為k的子樹的權(quán)值和最大為多少。

初步分析
這道題其實(shí)就是一道01背包問題只是是在樹上做而已。背包的總?cè)萘烤褪莐個(gè)結(jié)點(diǎn)（一定得剛好裝滿），每個(gè)物品的價(jià)值就是結(jié)點(diǎn)的權(quán)值w[i].注意，并不是隨便選取結(jié)點(diǎn)就行了。而是一定得是子樹。那么這一點(diǎn)我們要怎么實(shí)現(xiàn)呢。首先我們用dp[i][j]來表示以結(jié)點(diǎn)i為首的結(jié)點(diǎn)數(shù)為j的權(quán)值最大的一棵子樹。那么dp[i][j]的狀態(tài)方程怎么寫呢？dp[i][j]=max(dp[i][j],dp[i][j-w] dp[v][w])(v是結(jié)點(diǎn)i的子節(jié)點(diǎn)，1=<j<=cnt[i],0<w<j)注意我們是怎么保證dp[i][j]表示的是以結(jié)點(diǎn)i為首的子樹呢？新節(jié)點(diǎn)所能取得的最大結(jié)點(diǎn)數(shù)只能是j-1,因?yàn)閐p[i][1]始終代表的是結(jié)點(diǎn)i，所以才能保證都是以結(jié)點(diǎn)i為首的子樹。而且由于是01背包所以我們的背包容量j從大到小更新，這樣保證所有的小值都是上一次子節(jié)點(diǎn)的更新值而不是重復(fù)使用當(dāng)前結(jié)點(diǎn)的值(不然的話就變成完全背包了)。

直接上代碼

#include <iostream>#include <string.h>using  namespace std;const int MAX_N=110;const int MAX_M=220;int w[MAX_N];int dp[MAX_N][MAX_N];int cnt[MAX_N];int n,k,answer=0;//我們這里用圖來儲(chǔ)存樹，在遍歷的時(shí)候通過一個(gè)father參數(shù)就可以轉(zhuǎn)化為樹了。沒有必要用一個(gè)father數(shù)組來儲(chǔ)存int ans=0;int head[MAX_N];struct edge{    int v;    int next;}eid[MAX_M];void insert(int u,int v){    eid[ans].v=v;    eid[ans].next=head[u];    head[u]=ans  ;}int read(){    int w=1,s=0;    char ch=getchar();    while(!isdigit(ch)){        if(ch=='-'){           w*=-1;        }        ch=getchar();    }    while(isdigit(ch)){        s=(s<<1) (s<<3) ch-48;        ch=getchar();    }    return s*w;}int dfs(int node,int father){    cnt[node]=1;    for(int i=head[node];i!=-1;i=eid[i].next){        int v=eid[i].v;        if(v==father) continue;        cnt[node] =dfs(v,node);    }    dp[node][1]=w[node];    for(int i=head[node];i!=-1;i=eid[i].next){        int v=eid[i].v;        if(v==father) continue;        for(int j=cnt[node];j>=1;--j) {            for (int m = 0; m <=cnt[v] && m<j ;   m) {                dp[node][j] = max(dp[node][j], dp[node][j - m] dp[v][m]);            }        }    }    answer=max(answer,dp[node][k]);    return cnt[node];}int main() {    while(scanf("%d %d",&n,&k)!=EOF) {        for (int i = 1; i <= n;   i) {            w[i] = read();        }        memset(head, -1, sizeof(head));        ans=0;        for (int i = 0; i <MAX_N;   i) {            for (int j = 0; j <MAX_N;   j) {                dp[i][j] = 0;            }        }        for (int i = 1; i <= n - 1;   i) {            int x, y;            x = read() 1;            y = read() 1;            insert(x, y);            insert(y, x);        }        dfs(1, -1);        cout <<answer<<endl;        answer=0;    }    return 0;}