胡闹 tree

题目大意

给你一棵$n\le10^5$的树,你分别有白链、黑链$B,W\le30000$条。

你要把树上的点染成黑白。如果一条白链锁包含的点都被染成了白色,那你会的得到这条白链的奖励,黑链同理。

求最大奖励。

Luogu 2597 [ZJOI2012 灾难]

传送门

题目大意

一个食物网有$N$个点,代表$N$种生物,如果生物$x$可以吃生物$y$,那么从$y$向$x$连一个有向边。这个图没有环。

图中有一些点没有连出边,这些点代表的生物都是生产者,可以通过光合作用来生存; 而有连出边的点代表的都是消费者,它们必须通过吃其他生物来生存。

如果某个消费者的所有食物都灭绝了,它会跟着灭绝。

我们定义一个生物在食物网中的“灾难值”为,如果它突然灭绝,那么会跟着一起灭绝的生物的种数。

举个例子:在一个草场上,生物之间的关系是:

img

  • 如果羊都死了,那么狼会因为没有食物而灭绝,而小强可以通过吃牛、牛可以通过吃草来生存下去。所以,羊的灾难值是$1$。

  • 但是,如果草突然灭绝,那么整个草原上的$5$种生物都无法幸免,所以,草的灾难值是$4$。

给定一个食物网,你要求出每个生物的灾难值。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×