Problem’s Website

普通平衡树

Solution

首先这道题可以用多种方法来解决，本篇题解用的是最low的$Treap$，以后可能会另外说明其他几种解法。

Problem’s Website

天天爱跑步

Solution

这道题的题意还是很好理解的。

做法好像有很多种，因为我是个 菜鸡 ，所以就说一种比较$low$的做法。

Problem’s Website

运输计划

Solution

首先这是一道NOIP的压轴题。

题面好长啊，不少废话，一句话题意：

给定一棵树和m个任务（从$u$点到$v$点），可以使树上的一条边边权为0，让这m个任务中边权之和的最大值最小。

Problem’s Website

SDOI_2014旅行

Solution

这道题考察了两个知识点，一个是树链剖分，另一个是动态开点线段树。

树剖不会的同学请点击这

$Day0$

上午坐车去山外，路途比较顺利，$1h30min$就到了，相比之前快了不少。

学校环境还行，宿舍设施一般，但有电、有热水。但令我吃惊的是，宿舍里没有脸盆。。。

Problems Website

• SDOI_2011染色

Problem’s Wensite

• JLOI_2014松鼠的新家

  Solution

• 这道题有两种解法，一种为树上差分，另一种为树链剖分，下面我简单解释一下。

Problem’s Website

• NOI_2015软件包管理器

  Solution

• 一道经典的树链剖分题，我们把有依赖关系的软件包用树联系起来，对其进行树剖，设1为已安装，0为未安装，赋值前统计1的个数，赋值后取差值即可。
• 这道题正解是线段树维护，但本菜鸡为了复习ODT，于是就开O2写了个ODT过了这道题。。。
• 这道题用ODT维护和线段树差不多，核心就是assign函数，也是ODT复杂度的保证。

Problem’s Website

• 模板_树链剖分
• ZHOI2008_树的统计

  Solution

• 树链剖分前置知识：
  • 线段树
  • 树的dfs遍历
• 以上内容不会的同学可以先去学习一下，特别是线段树，我的其他几篇Blog有对其的介绍。

Problem’s Website

• 248