首页 > 代码库 > Codeforces 743D 树形dp
Codeforces 743D 树形dp
D. Chloe and pleasant prizes
题意:一棵树,以结点1为根结点悬挂在墙上,每个点有一个权值。选两条边切断,要求:刚好掉下两份结点,且两份不能属于同一子树。求两份结点可能的最大权值和。
tags:裸的树dp。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 200005;const ll inf= -1e18;int n;ll sz[N], dp[N][2]; //dp[u][0]表示u子树上只取下一份子树的最大值,dp[u][1]表示u子树上必须取下两份子树的和的最大值vector<int > G[N];void dfs(int u, int fa){ dp[u][0]=dp[u][1]=inf; for(auto v : G[u]) if(v!=fa) { dfs(v, u); sz[u]+= sz[v]; dp[u][1]=max(dp[u][1], dp[v][1]); //状态转移 if(dp[u][0]!=inf) dp[u][1]=max(dp[u][1], dp[u][0]+dp[v][0]); dp[u][0]=max(dp[u][0], dp[v][0]); } dp[u][0]=max(dp[u][0], sz[u]);}int main(){ scanf("%d", &n); rep(i,1,n) scanf("%lld", &sz[i]); int u, v; rep(i,1,n-1) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); if(dp[1][1]==inf) puts("Impossible"); else printf("%lld\n", dp[1][1]); return 0;}
Codeforces 743D 树形dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。