南宁网站网站建设,做网站衡水,龙岗网络营销网站制作哪里好,php网站开发案例论文题目
没有上司的舞会 - 洛谷 思路
这是一道非常裸的树形DP#xff0c;对于初学树形DP的OIer来说#xff0c;是一道十分良心的题
我们可以设: dp[x][0]表示以x为根的子树,且x不参加舞会的最大快乐值 dp[x][1]表示以x为根的子树#xff0c;且x参加了舞会的最大快乐值 则有 …题目
没有上司的舞会 - 洛谷 思路
这是一道非常裸的树形DP对于初学树形DP的OIer来说是一道十分良心的题
我们可以设: dp[x][0]表示以x为根的子树,且x不参加舞会的最大快乐值 dp[x][1]表示以x为根的子树且x参加了舞会的最大快乐值 则有 dp[x][0] sigma{max(dp[son][0],dp[y][1])} (son是x的儿子) dp[x][1] sigma{dp[son][0]} h[x] (h[x]是x参加的快乐值) 先找到唯一的树根root
则ans max(dp[root][0],dp[root][1]) 代码
#includebits/stdc.h
using namespace std;
int u,v,n,h[1000001],dp[100001][2],gen;
bool vis[100001];
vectorint vec[100001];
void dfs(int x)
{vis[x] 1;dp[x][1] h[x];for(int i 0;i vec[x].size();i){int son vec[x][i];if(vis[son] 0){dfs(son);dp[x][0] max(dp[son][1],dp[son][0]);dp[x][1] dp[son][0];}}
}
int main()
{cinn;for(int i 1;i n;i) cinh[i];for(int i 1;i n;i){cinuv;vec[v].push_back(u);vis[u] 1;}for(int i 1;i n;i)if(vis[i] 0){gen i;break;}memset(vis,0,sizeof(vis));dfs(gen);coutmax(dp[gen][0],dp[gen][1]);return 0;
}
4.结语
如果对您有帮助的话记得点个赞支持一下QwQ疯狂明示
