【bzoj2599】[IOI2011]Race

2014年9月7日3,7722

Description

给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.

Input

第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数 表示最小边数量 如果不存在这样的路径 输出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

2

题解

这题有点怪的点分治。。。

我的做法也比较逗,就是开一个100W的数组t,t[i]表示权值为i的路径最少边数

找到重心分成若干子树后, 得出一棵子树的所有点到根的权值和x,到根a条边,用t[k-x]+a更新答案,全部查询完后

然后再用所有a更新t[x]

这样可以保证不出现点分治中的不合法情况

把一棵树的所有子树搞完后再遍历所有子树恢复T数组,如果用memset应该会比较慢

 

 

  • %%%hzwer%%%2016年1月7日 上午12:48 回复

    为什么“这样可以保证不出现点分治中的不合法情况”???

    #1  
    • hzwer2016年1月7日 下午11:10 回复
      admin

      一棵一棵子树来咯,我写的不合法情况指的是起始点均在同一个子树内,路径经过根的情况

      #11