stdKonjac's Blog

 要做到不可替代,就要与众不同。

【偷钱】

题目描述

某高富帅城市有 N 个住户,每个住户有一定量的钱财。城市里有 N-1 条道路,每条道路连接两个住户,保证每两个住户都能直接或间接互相到达。
现一屌丝准备劫富济贫。一开始,他可以偷到任何住户的钱。但是一旦偷窃了一个住户,与他直接相邻的所有住户都会警惕起来。便偷窃不了了这些住户。
由于是屌丝,所以智商不足,需要你们帮他推测最多能偷窃多少钱?

输入格式

第一行输入一个数 N,表示住户个数。
第二行有 N 个用空格隔开的整数 ai ,表示第 i 个住户家里可以偷取的钱财。
接下来 N-1 行,每行两个整数 a,b 表示一条连接 a,b 两个住户的道路。

输出格式

输出仅一个整数,表示最多能偷的钱数量。

样例数据 1

输入

4
3 4 3 1
1 2
2 3
3 4

输出

6

备注

【数据范围】
30% 数据,n<=20 ;
100% 数据,n<=100000 。

开始没理解N个点N-1条边并且N个点可以互相到达这个条件的隐藏含义真是无限悲伤!这不就是没有环嘛!还花了1个小时去想环或者孤立点的情况真是蠢哭了TAT 知道了没环直接一路树形DP下去就行了,dp[i][0]表示不偷i点,dp[i][1]表示要偷i点,方程跟“没有上司的舞会”那道题基本一样,剩下的就没啥了,试了下双向边任意点开始DP,效率跟单向边相差不大(还快些?)

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.