哒哒哒哒哒

分类

最小生成树(1) 最短路(1) 未归档(121) 题解(2)

/ 注册

全部文章（共1篇）

P2495 [SDOI2011]消耗战 lca倍增+虚树+树形dp

题目：给出n个点的树 q次询问问切断 k个点（不和1号点联通）的最小代价是多少思路：树形dp sum[i]表示切断i的子树中需要切断的点的最小代价是多少 mi[i]表示1--i中的最小边权 sum[i]=min(mi[i],sigma(min(mi[v],sum[v]) (v∈i.so...

树形dp LCA 虚树 dfs序欧拉序

2019-03-31

0 428