萌新求助自出题

学术版

喵仔牛奶 @ 2023-03-05 16:16:25

  • 给定 n 点 m 边的 DAG，每个点都有一个点权，求每个点可以到达的点的点权和。

by CreutzWilknare @ 2023-03-05 16:20:11

不可做。next

by liucr @ 2023-03-05 16:22:45

不可做。next

by 5k_sync_closer @ 2023-03-05 16:23:08

@Karasu 这个为啥做不了啊，建反图然后拓扑不对吗

by jijidawang @ 2023-03-05 16:25:59

@5k_sync_closer 会算重吧

by _l_l_ @ 2023-03-05 16:29:59

不可做。next

by kyEEcccccc @ 2023-03-05 16:30:46

我同学说强于DAG路径计数

by 5k_sync_closer @ 2023-03-05 16:31:28

@jijidawang wssb。那用一点科技，每个点上维护线段树合并，应该就可以了吧。

by CreutzWilknare @ 2023-03-05 16:33:06

做完代码发我一份我拿去申个图灵奖玩玩

by critnos @ 2023-03-05 16:36:30

线段树合并假的

by 5k_sync_closer @ 2023-03-05 16:37:01

假了。每个点上的线段树节点数是 O(n) 的。

|