After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, t
Description 一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身 Input 输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有 一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整
Description聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one di
题目描述在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。 输入输出格式输入格式： 输入初始状态，一行九个数字，空格用0表示 输出格式： 只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据) 输入输出样例输入样例#1：283104765 输
Input Output Sample Input 6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6Sample Output 5 2
2 5
4 1
6 0Hint 不算难的LCA，对于三个人两两求出LCA并根据深度计算即
相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。 Input 输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。 每组数据首先是一个整数C(C <=
题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和 输入输出格式输入格式： 第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含N个非负整数，分别依次
给你一个m*n的格子的棋盘，每个格子里面有一个非负数。 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。 Input 包括多个测试实例，每个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50) Output 对于每个测试实例，输出可能取得的最大的和 Sample Input 3 3
75 15 21
75 15 28
34 70 5Sample Output 188
Wormholes Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 55119 Accepted: 20556 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to
Rockdu's Blog