前置知识 1 前置知识 2 （一些促进理解图可以看一下别人的） # 树剖： 前置基础：DFS 序， 树形 DP，线段树，链式前向星…… 树链剖分 就是对一棵树分成几条链，把树形变为线性，减少处理难度 需要处理的问题： 将树从 x 到 y 结点最短路径上所有节点的值都加上 z 求树从 x 到 y 结点最短路径上所有节点的值之和 将以 x 为根节点的子树内所有节点值都加上 z 求以 x 为根节点的子树内所有节点值之和 # 概念： 重儿子：对于每一个非叶子节点 (x)，在它的儿子 (y,z……) 中 以儿子 (y，z……) 为根的子树大小最大的节点 (y,z…… 中的一个) 为该节点的重儿子...

# 树形问题 为什么出这么一个博文呢：我今天听课以及题解看的不是很懂，sososo 我想写个（现在还在上课但我没读题，下课补吧……）。 P2016 战略游戏 一道简简单单的树上 DP 不想点链接那么就看这里： 题意：他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。 注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。 请你编一程序，给定一树，帮 BobBobBob 计算出他需要放置最少的士兵。 输入：第一行一个整数 nnn，表示树中结点的数目。 第二行至第n+1n+1n+1...