Shortest Path 题目链接 题意 给一棵树、让把树分成两半（不是砍成两半、是节点分成两半） 也就是分成n/2 个 A -------- B 然后让他们的总的权值最小 保证n是偶数 怎么做？ 权值最小是忽悠人的。。 因为只能分成一种情况 首先叶子结点肯定跟他的父节点相连。。（因为必须得分成n/2对 不能有一个节点落下 如果叶子不跟他的父节点在一起、那么就没有节点跟她相连了） 所以唯一的 于是就得到如果这棵子树的节点个数是奇数 那么这个子树的根节点就肯定跟他的父亲节点相连 肯定会想到这种特殊情况：  这个显然无解、题目是不会给出的 代码： #include<stdio.h> ...

Innumerable Ancestors 题目链接 题意 给出一棵树（1为根）、有m次询问；每次询问给出两个节点集合、从这每个集合中挑出一个节点（可能相同）、让求这两个节点的lca最深是多少。 怎么做？ lca很好求，倍增， 但是节点怎么挑？ 这里很巧妙？ 或许是我见识短 求出这棵树的dfs序 然后把第一个集合里的节点按照dfs序排序，然后就可以枚举第二个集合的节点二分第一个集合找出离这个节点最近的节点，要么dfs序比当前节点相等、大要么小、就这两个节点为什么是两个？不是三个吗？ 因为相等的话就不用判断大或小了， 这个思路反正我是想不出来，，，害~ 代码： #include<stdio...

替罪羊树 替罪羊树 是啥？ 就是一个平衡树，只不过没有旋转操作 那遇到不平衡的咋办呢？ 重构。 怎么重构？先求出不平衡子树的中序遍历（这个中序遍历肯定是有序的递增的）于是就可以分治建树，取中间那个点当根左边的当左子树、右边的当右子树……递归下去 于是就把不平衡的子树变成平衡的子树。 例题：洛谷模板 P3369 几种操作 结构体存的信息: struct Node {  int l,r;//左右节点编号 int val;//当前节点的值 int flag;//当前节点是否被删除 删除为0 没删除为1 int size;//size 是这颗子树的大小（包含被删除的节点） int fact;//fac...

D. Complete Mirror 题目链接 题目大意 给出一棵树，让你找一个根节点，使每个到根节点距离相等的点的度数都相等。 怎么做呢？ 想一下答案有几种情况： 1、所有叶子节点。这个应该都可以想到 不是叶子结点的情况：  又是歪歪又扭扭的图 这个图的答案只能是4。 所以： 2、树的重心。这他妈谁想得到，知道有这种情况 没想到这这是个重心 知道这个以后就简单了： 先判断重心，然后枚举叶子节点、就好了。 但是枚举全部叶子节点肯定超时（菊花图）。 然后想一想。距离重心距离相等的叶子节点只用记一个就好。如果这个可以那么别的肯定也可以，这些是等价的。 所以就用vector存叶子节点就好。 所以就简...

Serval and Rooted Tree 题目链接 题目大意 给一棵有根树，设有k个叶子节点，给所有的叶子节点标号1~k；然后每个非叶子节点都有一个得到当前节点标号的方法，就是取他的所有子节点的最大值或最小值（取决于输入）；问根节点能得到的最大的标号是啥。 刚开始不会做，想着贪心可不可以做，于是想了半天，啥求都不会 于是瞅了一眼题解，dp做，向来不怎么dp的我很是懵逼，还是不知道怎么dp，于是又看了看，如下： dp[i] 表示第i个节点的标号是他所有子节点标号中的第几大，也就是1~k中比它大的数至少有dp[i] - 1个 于是 叶子结点的dp值就是1。 如果操作是得到子节点的最大值，那么当...

吉老师线段树 这个是干啥的？ 其实就是个线段树，我也不知道为什么叫吉老师线段树 简单例题：hdu5306 三种操作： 0 l r x 把 l ~ r 区间里大于 x 的数变成 x 1 l r 求 l ~ r 区间里的最大值 2 l r 求 l ~ r 区间和 题解: 线段树里记一个最大值max、最大值的个数num、次大值max2、区间和sum。 查询很好查询，主要是维护 更新： 如果当前区间最大值小于等于x 那么就不用修改。 如果当前区间最大值 > x > 次大值 那么只用把最大值改为x、记tag、更新和就好 其他情况继续往下走、 但是时间复杂度？？？为什么我感觉很高。 想一哈： ...

我好菜 （这三个字写这么大完全是为了提醒自己 hhhh 竟然这都不会） 树形dp； 不懂得如何推出状态表达式 （即使再简单）看见题目就无从下手！！！有点烦 所以决定多刷一点dp题， 先看了最基础的： 洛谷P1352 这个题其实挺简单的，但是我是真的废。。。 题意: 给出一棵树，每个节点有自己的权值，选择出一些点，选择点的时候如果选择了当前节点的父节点则不能选择当前节点，这很显然的树形dp，可能是我做dp题目太少了吧，连dp数组都不知道该代表点啥。 于是看了题解。 dp[i][0] 代表这颗子树不选 i 节点 能选出的最大权值。 dp[i][1] 代表这颗子树上选择 i 节点能选出的最大权值。 ...

P2015 二叉苹果树 题目链接 题意： 给一棵树，每个边都有权值，选择一些边删除，剩余m条边。问删除后所有变得权值和最大是多少？ 树形dp 01背包问题； dp数组：dp[maxn][maxn] ； dp[x][i] 代表x为根节点的子树上有i条边的最大权值； 转移方程： num[x]为子树上目前有多少边，为什么说目前呢？ 因为子节点还没遍历完， for (int j = min(m,num[x]); j > 0; j -- ) for (int k = 0; k <= min(j - 1,num[v]); k ++ ) dp[x][j] = max(dp[x][j],dp[v]...

树形dp 又是树形dp。。。 题目链接 题意: 给一棵树，给出边权（边权为距离）把m个点标记为黑色，让求黑色点两两之间的距离加白色点两两之间的距离的最大值。 怎么做呢？我还是菜了呀 <mark>dp[x][i] 代表x子树上有i个黑点的对答案的贡献的最大值。</mark> 然后就没有然后了 ， 就不会了。 于是看题解 题解： 这个题也是背包。 于是写出了这个： for (int j = min(num[x],m); j >= 0; j -- ) {  for (int k = 0; k <= min(j,num[v]); k ++ ) {  if(dp[x]...

Treepath 题目链接 题意: 给一棵树，让求两个点距离为偶数的点有多少对。 题解： 两个点的距离可以换为：d[x] + d[y] - 2 * d[lca];(d数组为到根节点的距离) 于是后面的-2*d[lca]不影响奇偶性。所以到根节点奇偶性相同的点可以组成一对。就很简单了。 代码: #include<stdio.h> #include<algorithm> #include<vector> using namespace std; const int maxn = 1e5+5; int a[maxn]; vector<int> vv[m...

树上启发式合并 这个是啥？ 先说一下并查集的启发式合并： 并查集的启发式合并就是把集合小的并到集合大的上去。(按秩合并是把低的并到高的上面去) 于是树上的也差不多： 就这样一个优化的思路。把大的并到小的上去 树上： 什么是大的：重儿子的那个子树。 小的: 轻儿子的那几个子树。 就是算答案的时候把轻儿子的贡献并到重儿子的贡献上去于是就有了当前根节点的答案。 说说例题吧： cf600E 题目大意: 给出一棵树，根节点为1；每个节点都有一个颜色、求以每个子树上颜色最多的颜色代号和。就是 如当前子树上1号颜色最多，答案就是1 。如果1号、2号颜色的节点一样多的话，答案是1+2 = 3； 思路: col...

CF 621D 题目链接 题目大意: 给一个图，n个点m个边，给出k个特殊点，保证图联通，让在特殊点中选一对点连起来，求连完后的1到n节点的最短路的最大值。 ，，，怎么做呢？ 朴素做法： 显然是预处理1~每个结点的最短路，n到每个结点的最短路，然后枚举k里的两个节点，连起来，取最大值，然后最后跟原来的最短路取最小值就好了，但是这个复杂度是k^2。 显然不行，于是想一下怎么优化，，， 就是这里，想不到了，短路了，自闭了，掉分了，没了。。。 赛后看大佬题解： 设选的点为x和y，1到i节点的最短路为dis[0][i] n到i节点的最短路为dis[1][i]； 过x，y的最短路为min(dis[0][...

cf div2 c2 题目链接 自闭了 这个题题意: 给一个数组，让构造一个左边跟右边不能同时有大于这个数的（左边右边不一定是挨着的）、给出的数组是当前位置的最大值。构造出来的数组的和尽可能大 很明显 要么递增、要么递减、要么找个峰值左边递增，右边递减。 第一二种情况可以归为第三种情况。 比赛时候想到了遍历一遍想办法弄出左边递增的最大值跟右边递减的最大值 要找出i位置从1~i是递增的最大值，怎么找？ 比赛的时候想到了记录前一个比当前数小的数。然后再记录后一个比当前小的数。 设他前面比它小离他最近的这个数是x于是得到1到 i 位置上的最大值就是1~x的最大值加（i - x）* a[i]。 但是比...

D. Array Without Local Maximums 题目链接 题意 给一个数组，给出一个数组，（1e5） 包含数字 1~200 或 -1 -1代表这个数字不知道是多少，让构造数组，把-1填上 ，使得数组里的每一位数字都有旁边的两个数至少有一个大于等于这个数。也就是 ai≤max(ai−1,ai+1)，问有多少种方法构造。 显然是dp 但是就是想不到怎么写， 大佬们都说这是很简单的dp。。。 题解 dp数组： dp[3][200][100005] 代表的意思： 3代表与前一位的关系，0 ： 小于前一位， 1 : 等于前一位， 2 : 大于前一位。 200 代表当前数字是多少， 后面那...