树的分治

dzy posted @ 2014年2月16日 16:15 in 专题 with tags 点分治 , 1798 阅读

太弱了。。挖坑。。

 

 

  • bzoj2599[IOI2011]race：给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.

设当前分治的根为root。d[i]表示i到root的距离，dep[i]表示i到root的深度，f[i]表示到root的路径为i需要的最小边数，tag[i]表示是否存在从一个点到root的路径为i（这样可以重复利用f数组）。枚举root的子节点v，第一个v用来更新tag数组和f数组，对于后面的v，先更新答案，然后更新tag和f数组即可。

  • bzoj1316树上的询问：同上一题，10000个点，100个询问。

方法同上。（注意K可能是0，极坑）

  • bzoj2870最长道路tree：坑

 

  • bzoj2152聪聪可可：

貌似有O(n)的treedp我不会太弱QUQ。点分即可。记录%3=0.1.2的个数，乘一下就好。

  • bzoj1758[wc2010]重建计划：坑

 

  • bzoj1267Kth Number I：

边分好了。每次得到两个字树的答案，维护一个大根堆每次把大的插进答案堆。答案堆是个小根堆。

 

  • USACO2013 open T2 ： 坑

 

  • cc prime dist：坑

 

 

Small_feed 评论 (7)
1
[回复]
Avatar_small
Digital Ali 说:
2021年9月13日 18:56

Awesome article! I want people to know just how good this information is in your article. It’s interesting, compelling content. Your views are much like my own concerning this subject. soap2day

2
[回复]
Avatar_small
Digital Ali 说:
2021年9月15日 16:53 Thanks for taking the time to discuss this, I feel strongly that love and read more on this topic. If possible, such as gain knowledge, would you mind updating your blog with additional information? It is very useful for me. best CBD salves
3
[回复]
Avatar_small
Digital Ali 说:
2021年9月15日 19:12

Hi, I find reading this article a joy. It is extremely helpful and interesting and very much looking forward to reading more of your work.. 123movies

4
[回复]
Avatar_small
SEO 说:
2021年10月01日 19:29

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. browse around this website

5
[回复]
Avatar_small
best ergonomic chair 说:
2021年10月02日 21:38

Be careful while buying a chair for back pain. Here we suggest you best ergonomic chair for watching TV. These are highly recommended chairs. Chose a chair and get rid of your back pain.

6
[回复]
Avatar_small
SEO 说:
2021年10月10日 00:23

Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. SEO เว็บพนัน

7
[回复]
Avatar_small
SEO 说:
2021年10月30日 23:22 Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.Thanks bosbandarq

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter