NOI模拟17解题报告

链型网络

「問題要約」
给定一个无自环、无重边的无向图,每次加一条边或者询问有多少个点可以满足删去之后剩下的每一个连通块都是链。
「問題分析」
显然有2个度大于等于4的点无解。
那么如果所有点的度数都小于等于2,我们只需要判断每个连通块是否无环。
用并查集即可。
具体实现是当有一个点的度数大于等于3时,我们建立四个新图出来,分别去掉当前点与其邻接点。
之后判断即可。

物流

「問題要約」
给你一棵树,你可以在树上选出一些点建立Power station,建立发电站有代价K,每个不建立发电站的点的代价是一个关于到距离最近的发电站的距离的函数,且费用单增,求最小总费用。
「問題分析」
表示距离i点最近的发电站是j,i的子树中的总代价之和的最小值。

时间复杂度

花园

「問題要約」
给你一棵树,每次修改一个点的颜色或者询问路径上指定颜色的点的个数。
「問題分析」
因为树的结构不变,所以对树进行树链剖分。对于每个颜色动态开一棵线段树,在树上查询路径和即可。主席树套树状数组也可以做。
时间复杂度