鲍勃喜欢玩电脑游戏，特别是战略游戏，但有时他找不到解决问题的方法，这让他很伤心。 现在他有以下问题。 他必须保护一座中世纪城市，这条城市的道路构成了一棵树。 每个节点上的士兵可以观察到所有和这个点相连的边。 他必须在节点上放置最少数量的士兵，以便他们可以观察到所有的边。 你能帮助他吗？ 例如，下面的树： 只需要放置 1 名士兵（在节点 1 处），就可观察到所有的边。 输入...

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。 这棵树共 N 个节点，编号为 1 至 N，树根编号一定为 1。 我们用一根树枝两端连接的节点编号描述一根树枝的位置。 一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。 这里的保留是指最终与1号点连通。 输入格式 第一行包含两个整数 N 和 Q，分别表...

如果一个数 x 的约数之和 y（不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。 例如，4 可以变为 3，1 可以变为 7。 限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。 输入格式 输入一个正整数 n。 输出格式 输出不断进行数字变换且不出现重复数字的最多变换步数。 数据范围 1≤n≤50000 ...

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。 请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。 输入格式 第一行包含整数 n。 接下来 n−1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。 输出格式 输出一个整数，表示所求点到树中其他结点的最远距离。 数据范围 1≤n≤...

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。 现在请你找到树中的一条最长路径。 换句话说，要找到一条路径，使得使得路径两端的点的距离最远。 注意：路径中可以只包含一个点。 输入格式 第一行包含整数 n。 接下来 n−1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。 输出格式 输出一...

将一个 8×8 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了 (n−1) 次后，连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行) 原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。 现在需要把棋盘按上述规则分割成 n 块矩形棋盘，并使各矩形棋盘总分的均方差最小。 均方差 ，其...

给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。 将这个凸多边形划分成 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。 输入格式 第一行包含整数 N，表示顶点数量。 第二行包含 N 个整数，依次为顶点 1 至顶点 N 的权值。 输出格式 输出仅一行，为...

设一个 n 个节点的二叉树 tree 的中序遍历为（1,2,3,…,n），其中数字 1,2,3,…,n 为节点编号。 每个节点都有一个分数（均为正整数），记第 i 个节点的分数为 di，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：      subtree的左子树的加分 × subtree的右子树的加分 ＋ subtree...

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 N 颗能量珠。 能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。 并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。 因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。 如果前一颗能量珠的...

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。 请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算： 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。 输入格式 第一行包含整数 n，表示共有 n...