伶俐荷花

文章
4
资源
0
加入时间
4年1月9天
bzoj2599: [IOI2011]Race 点分治

bzoj2599: [IOI2011]Race 点分治

题意：给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000明显点分治，但是愚蠢的我并没有想到怎么分治。。%hzwer。 开一个t[i]表示整棵树中权值和为i的路径有多少条，那么我们分治每一颗树的时候，再算出子节点到当前根的dis[x]权值距离和d[x]点数距离，然后就可以直接更新了ans=min(ans,t[k-dis[x]]+d[
bzoj 2024-07-17

他的专栏

正则表达式（0）
PHP编程（0）
Mysql（0）
JavaScript（2）
缓存（1）
bzoj（1）

他的归档

2024年07月（1）
2024年01月（1）
2022年04月（2）

热门文章

1
JavaScript cookie的设置获取删除详解
2
ext combobox动态加载数据库数据(附前后台)
3
几句话说明Redis缓存穿透、击穿、雪崩、Redis哨兵几句话说明Redis缓存穿透、击穿、雪崩、Redis哨兵
4
bzoj2599: [IOI2011]Race 点分治