首页 > 其他分享 >洛谷 P1352 没有上司的舞会

洛谷 P1352 没有上司的舞会

时间:2024-06-13 11:12:40浏览次数:25  
标签:舞会 洛谷 int head nex cnt P1352 dp happy

题目链接:没有上司的舞会



思路


题解

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;

int dp[N][2], happy[N], subordinate[N], cnt, head[N], nex[N], edge[N];
// 链式向前星存储边
void add(int x, int y) {
  nex[++cnt] = head[x];
  head[x] = cnt;
  edge[cnt] = y;
}

// 树形dp
void dfs(int x) {
	dp[x][0] = 0;
	dp[x][1] = happy[x];
	for (int i = head[x]; i; i = nex[i]) {
		int to = edge[i];
		dfs(to);
		dp[to][1] += dp[to][0];
		dp[to][0] += max(dp[to][0], dp[to][1]);
	}
}

int main() {
  int n, l, k;

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> happy[i];
  }
  for (int i = 1; i < n; i++) {
    cin >> l >> k;
    add(k, l);
    subordinate[l] = true;
  }

  int root;
  for (int i = 1; i <= n; i++) {
    if (subordinate[i] == false) {
      root = i;
      break;
    }
  }

  dfs(root);
  cout << max(dp[root][0], dp[root][1]);

	return 0;
}

标签:舞会,洛谷,int,head,nex,cnt,P1352,dp,happy
From: https://www.cnblogs.com/againss/p/18245503

相关文章

  • 洛谷 P1219 八皇后
    题目链接:八皇后思路    这是一个典型的搜索题目,从前往后依次枚举行数,从第一行开始依次枚举皇后的纵坐标,并判断当前坐标是否满足题目要求,满足题目要求则标记将答案存储,并继续向下枚举下一行。由分析可得每条对角线上的任意一点的横纵坐标满足公式i-j+n的值与对角......
  • 洛谷P1601 A+B Problem(高精)
    #include<iostream>#include<string>#include<cstring>#include<cstdio>usingnamespacestd;constintN=1005;structbign{intlen,s[N];bign(){memset(s,0,sizeof(s));len=1;}bign(intnum){*this=num;}......
  • 子集和加总问题(从洛谷博客同步)
    给出\(\{a_{1\dotsn}\}\),找出一个子集和为\(0\)。这是NPC的,当\(|a_i|\leqn\)的时候可以\(n^3\)背包,当然地可以使用bitset压位至\(\frac{n^3}w\)。值域还是太难受了,考虑怎么压下来值域,因为和为\(0\),值域又是\(n\),通过调整顺序总是存在一种方案使得值域在\([-......
  • 一般图边覆盖计数(从洛谷博客同步)
    今天模拟赛中出现了一个题,需要对一个\(n\)个点,\(m\)条边的图做边覆盖计数,边覆盖是一个边集\(S\subseteqE\)使得任意一个点\(i\)都存在一条边\((u,v)\inE\)满足\(u=i\)或\(v=i\),即覆盖所有的点。\(n\leq40,m\leq60\),1s512M。然后被我使用神秘做法冲过去了(然后莫......
  • 数学森林/洛谷P1750 出栈序列
    原创新思路求解出栈序列问题。问题描述:数学家小王经过千辛万苦长途跋涉终于来到了数学森林。无奈森林入口有很多个小矮人镇守。小矮人拿出一套题目让小王抽取一道题目说解出题目方能进入数学森林。题目如下:给定一个大小为c(最多可以同时存储c个元素)的堆栈,输入n个入栈的数,请输......
  • 洛谷估值
    达成时间基础信用练习情况社区贡献比赛情况获得成就总咕值202406031005441193024420240527100532719302292024052010049282030227202405131004630213022720240506100472321302212024042910045172230214......
  • 洛谷P4017 最大食物链计数
    题目信息题目要求样例输入/输出 算法简介 要知道题目需要用到什么样的算法,首先得捋清楚题目的意思比如这个题目,我们读题后可以获得这样的信息:(1)节点之间构成有向边(2)所有边不会构成环(3)需要求的所有的边没有边权而且一定是从入度为零的节点到出度为零的节点基......
  • 洛谷1803 凌乱的yyy / 线段覆盖 【贪心】
    凌乱的yyy/线段覆盖题目背景快noip了,yyy很紧张!题目描述现在各大oj上有nnn个比赛,每个比赛的开始、结束的时间点是知道的。yyy认为,参加越多的比赛,noip就能......
  • 洛谷1090 合并果子 【贪心】
    [NOIP2004提高组]合并果子/[USACO06NOV]FenceRepairG题目描述在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出......
  • 关于洛谷获得数据怪谈
    免责声明:本文仅用于测试键盘性能,输入内容概不负责。在洛谷有时输入数据仅有几个数字,但是出于某些原因无法获得输入数据,但是手贱非常想要获得,于是尝试一种特殊方法。示例题目:P1014[NOIP1999普及组]Cantor表尝试提交以下代码:#include<iostream>usingnamespacestd;intn......