WNJXYKの博客

题目传送门：Maximum White Subtree 题目大意 给你一颗无根树，其节点被染成黑白两色。对于其任意一个节点 $v$，我们要求出某一个包含 $v$ 的联通块，使得联通块内白色节点 – 黑色节点数量最大。对于每一个节点，都输出最大化的差值是多少。 题解 这是一个树形DP，使用 […]

这题感觉很迷幻…… CSP 现场的时候按照 70 分写了个 DP，对拍了 1 个小时交上去只有 20 分。现在想起来，重写了一遍，直接就 100 了。 我觉得 CSP 201909 这一场比赛的问题很大。第三题题意严重不清楚，第四题和第五题的数据我认为都有锅。 题目大意 给你一颗有 n 个点的树，其 […]

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4033 题目大意 有一棵点数为 N 的树，树边有边权。给你一个在 0~ N 之内的正整数 K ，你要在这棵树中选择 K个点，将其染成黑色，并将其他的N-K个点染成白色 。 将所有点染色后，你会获 […]

传送门：http://vjudge.net/problem/16417 题目大意 一个以 根节点 为根的树，每个叶子节点有收益，每条边有花费。求在不亏本的时候，最多能使多少叶子节点与 根节点 联通。 题解 树形DP 先多叉转二叉（左兄弟右孩子），然后在二叉树上DP。F[i][k]表示以 i 为根的节 […]

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2196 题目翻译 一个N个节点的树，每条边长度，求每个节点到距其最远的节点的距离。 题解 以1为根，分别求出以i为根的子树中距i最长的距离和经过i的父亲的最长距离，答案就是这两个值求Max 代码 [cray […]

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5834 题目翻译 有一颗有N个节点的树，经过节点i得到V[i]点（只能得到一次），经过边i消耗C[i]点（可以重复消耗），问每个点可以获得的最大点数是多少。 题解 树DP 首先我们假装之询问点1。 我们记F […]

传送门：http://codeforces.com/contest/686/problem/D 题目大意 给定 n , q 表示在一棵大小为 n ，根为 1 的树上有 q 个询问。 接下来一行 n-1 个数 ，表示 2~n 每个节点的父亲。 接下里 q 行每行一个数字 x，表示询问以 x 为根的子数 […]

传送门：http://codeforces.com/contest/682/problem/C 题目大意 有一颗根为节点1的树，每条边有一个权值，每个点有一个a[i]值，对于一个节点V如果存在节点U使，V~U的路径长度大于a[V]，那么说明节点V是sad的。问要删除多少节点，才能使这棵树是不Sad的 […]

题目描述 byteland的王后深受百姓爱戴。为了表达他们的爱，国民们打算占领一个新的国家，并以王后的名字命名。这个国家有n座城市。城市之间有双向道路连接，且每两个城市之间有且仅有一条道路。每座城市对其拥有者来说都有一定的收益。尽管国民们非常爱戴他们的王后，他们并不一定会征服所有的城市献给她。他们只 […]