首页 > 代码库 > 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