哒哒哒哒哒

未归档

最小生成树(1) 最短路(1) 题解(2)

/ 注册

全部文章 / 未归档（共2篇）

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

Codeforces Round #526 (Div. 2) D. The Fair Nut and the Best Path 树上dp

D. The Fair Nut and the Best Path 题意：给出一张图点有权值边也要权值从任意点出发到任意点结束到每个点的时候都可以获得每个点的权值，而从边走的时候都要消耗改边的边权，如果当前值小于边的边权，就走不通，问从任意点出发到任意点结束的可以获得的最大权多少（其中到一...

dp 树形dp 树

2019-05-01

0 581