仙人掌[ZJOI2017]

题目描述https://www.luogu.com.cn/problem/P3687 题面里咋还有张图啊,就不放这了 题解首先,如果原图不是仙人掌,显然答案为0 如果原图是一棵树,那么我们可以选择若干条边不相交的路径,如果某条路径长度大于一,就将路径的两个端点间加一条边,那么这样构造出来的图一定是一个仙人掌 所以原问题实际在问有多少种方案用若干条边不相交的路径覆盖原图 设f[x]表示考虑x的...

快餐店[NOI2013]

题目描述小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的N个建筑中,这N个建筑通过恰好N条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中,也可...

历史[ZJOI2018]

题目描述&输入/输出格式[ZJOI2018]历史 题解首先,没有修改时的答案可以使用树形DP解决 上图中,红色数字表示$a_x$,蓝色数字表示$x$子树的点权和$sum_x$ 观察点$2$,显然只有$2,5,6$”崛起”时才有可能在$2$发动战争 显然,当操作顺序形如$5,2,5,6$时,会在$2$进行三次战争,为最大值。 再来看点$1$,其实我们可以把$2,5,6$三个点看作一个点...

世界树[HNOI2014]

题目描述题目背景太长不放 传送门 给你一棵$n$个节点的树,有$q$次询问,每次指定$m_i$个节点为关键节点;对于任意一个节点,它被距离自己树上距离最近的那个关键节点管辖;输出每个关键节点各管辖多少个节点 $n,, q \le 300000$,$\sum m_i\le 300000$ 题解看到$\sum m_i\le 300000$想到什么了?虚树! 所以我们把关键节点的虚树建出来,然后考...

选课[luogu P2014]

【题目描述】在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有$N$门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程$a$是课程$b$的先修课即只有学完了课程$a$,才能学习课程$b$)。一个学生要从这些课程里选择$M$门课程学习,问他能获得的最大学分是多少? 【输入格式】第一...

普通图论题

【题目描述】给定一棵$n$个点的树,标记出$m$个不同的点$s_1,s_2,s_3,\cdots,s_m$,对于每个点$s_i$求出剩下的标记点中哪个离$s_i$最近,输出距离。 【输入格式】第一行一个整数$n$。第$2\sim n$行每行两个整数$u,w$,第$i$行表示$i$与父亲$u$之间有一条权为$w$的边。 接下来一行一个整数$m$。接下来一行$m$个整数表示$s_1\sim s_...