江门网站免费制作,微商怎么做,德尔普网站建设,创建网站哪个好P1352 没有上司的舞会
题意#xff1a;
给你一个树#xff0c;每个点都有权值#xff0c;选择一些点使得权值和最大#xff0c;要求父亲节点和子节点不能同时选择
题解#xff1a;
经典树形dp dp[x][0]表示以x为根的子树#xff0c;且x不参加舞会的最大快乐值 dp[x][…P1352 没有上司的舞会
题意
给你一个树每个点都有权值选择一些点使得权值和最大要求父亲节点和子节点不能同时选择
题解
经典树形dp dp[x][0]表示以x为根的子树且x不参加舞会的最大快乐值 dp[x][1]表示以x为根的子树且x参加了舞会的最大快乐值 则dp[x][0] ∑{ max(dp[y][0],dp[y][1]) } (y是x的儿子) dp[x][1] ∑{ dp[y][0] } a[x] (y是x的儿子) 找到唯一的树根root ansmax(dp[root][0],dp[root][1])
代码
#includebits/stdc.h
using namespace std;
#define MAXN 6005
int a[MAXN];
int v[MAXN];
vectorint son[MAXN];
int f[MAXN][2];
void dp(int x)
{f[x][0]0;f[x][1]a[x];for(int i0;ison[x].size();i){int yson[x][i];dp(y);f[x][0]max(f[y][0],f[y][1]);f[x][1]f[y][0];}
}
int main()
{int n;cinn;for(int i1;in;i) cina[i];for(int i1;in-1;i){int x,y;cinxy;son[y].push_back(x);v[x]1;}int root;for(int i1;in;i)if(!v[i]) {rooti;break;}dp(root);coutmax(f[root][0],f[root][1])endl;return 0;
}
