贵阳网站建设技术托管,佛山市seo推广,学校网站网页模板,做网站中心上一次我们讲了二叉苹果树#xff0c;现在我们加一点难度#xff0c;从二叉变成了多叉苹果树。
这样子我们就不可以直接按照上次的方法DP#xff0c;我们其实可以发现#xff0c;我们可以用类似背包的思想求解#xff0c;这就是所谓的树上背包。
我们先加进第一个儿子来…上一次我们讲了二叉苹果树现在我们加一点难度从二叉变成了多叉苹果树。
这样子我们就不可以直接按照上次的方法DP我们其实可以发现我们可以用类似背包的思想求解这就是所谓的树上背包。
我们先加进第一个儿子来跟新1--m的解然后再让第二个进来更新这样子就求出来了。
下面是AC代码
#includebits/stdc.h
using namespace std;
int n,q,x,y,head[200],v[200],cnt,z,dp[110][110];
struct node{int dian,next,quan;
}edge[210];
void merge(int x,int y,int z){edge[cnt].diany;edge[cnt].quanz;edge[cnt].nexthead[x];head[x]cnt;
}
void dfsquan(int root,int fa){for(int ihead[root];i!-1;iedge[i].next){if(edge[i].dianfa) continue;v[edge[i].dian]edge[i].quan;dfsquan(edge[i].dian,root);}return;
}
void dfsdp(int root,int fa){for(int jq1;j1;j--){dp[root][j]v[root];}dp[root][0]0;for(int ihead[root];i!-1;iedge[i].next){if(faedge[i].dian) continue;int ckckedge[i].dian;dfsdp(ckck,root);for(int jq1;j1;j--){for(int k0;kj-1;k){dp[root][j]max(dp[ckck][k]dp[root][j-k],dp[root][j]);}}}
}
int main(){cinnq;memset(head,-1,sizeof(head));for(int i1;in-1;i){cinxyz;merge(x,y,z);merge(y,x,z);}dfsquan(1,-1);dfsdp(1,-1);coutdp[1][q1];
}
这里有两点注意
1.v[root]操作不应该放在循环里面否则会重复操作若为边权可以
2.转移方程中应为dp[root][j-k]而不是dp[root][j-k-1],因为root时已经把root点算进去了不用为root留空间。
接题 其实我们可以不用DP
我们可以先选任意一点DFS求出权值最大的子链我们可以证明权值最大的子链的端点之一一定是这个DFS后的端点。
下面进行证明 我们再来看看树形DP的解法
我们令f[i]表示以i为根的子树的最大子链有两种情况1.它经过i 2.他没有经过
对于经过i我们只要把以i为起点DFS的最大长度与第二大长度相加即可。
这里我们可以简化一下
我们令ans为答案值,dp[i]为以i为起点的最大权值我们在求dp[i]的同时维护ans即可。
其中相加操作dp[i]记录了到目前为止的最大值有点类似背包通过dp[i]dp[v]就实现了最大值与次大值相加的操作最后维护一下dp[i]即可。
下面是AC代码
#includebits/stdc.h
using namespace std;
#define int long long
struct node1{int dian,next;
}edge[200010];
int head[100010],n,a[100010],cnt,u,v,dp[100010],ans-10000000;
void merge(int x,int y){edge[cnt].diany;edge[cnt].nexthead[x];head[x]cnt;
}
void dfsdp(int root,int fa){dp[root]a[root];ansmax(ans,a[root]);for(int ihead[root];i!-1;iedge[i].next){if(edge[i].dianfa) continue;dfsdp(edge[i].dian,root);ansmax(ans,dp[edge[i].dian]);ansmax(ans,dp[root]dp[edge[i].dian]);dp[root]max(dp[root],a[root]dp[edge[i].dian]);}return;
}
signed main(){cinn;memset(head,-1,sizeof(head));for(int i1;in;i){scanf(%lld,a[i]);}for(int i1;in-1;i){scanf(%lld%lld,u,v);merge(u,v);merge(v,u);}dfsdp(1,-1);coutans;
}
