题目链接： https://www.luogu.org/problemnew/show/P4092 分析瞎扯—$O(Q \log^3 N)$解法 这道先yy出了一个$O(Q \log^3 N)$,的做法，先树链剖分。 对于加标记操作，找到那个点所在的链，将其$top$标记一下，然后该点到根节点区间和+1. 对于查询操作，先看这个点所在链有没有标记，如果没有，就一直向上跳直到找到一条标记了的链，然后
题目链接https://cn.vjudge.net/problem/HDU-2196 给定一棵树,求离每个节点最远的点的距离是多少 分析前置技能: 二次扫描与换根 不清楚的可以看一看之前POJ3585的博客或是自行了解 首先考虑先$O(N)$钦定点以之为根树形DP怎么做 太容易了,$f[now]$表示以$now$为根的子树中距$now$最远的距离 $f[now]=max(f[now],f[son]
题目链接https://cn.vjudge.net/problem/POJ-3585 找到一个点,如果其成为河水发源地,使整棵树的流量最大,有些河道会限制流量 真- 网络流 分析学到了一个船新骚操作—二次扫描与换根! 首先我们来$naive$的做法,枚举每个点作为发源地,然后进行一次树形DP $f[now]$表示在$now$为根的子树中的最大流量,那么根据题目定义 $f[now] = \sum m
题目链接https://www.luogu.org/problemnew/show/P3360 分析如果你做过https://www.luogu.org/problemnew/show/P1270这个的话发现这题只是在叶节点处加了个简单的背包… 首先发现这是一颗二叉树,这就资瓷了,转移时我们直接枚举给左子树分配多少时间就好了,然后到叶节点时跑个01背包就没事了 但是这个毒瘤输入让人不得不怀疑是UW
题目链接https://www.luogu.org/problemnew/show/P2014 分析巧妙的树上背包,$f[now][p]$表示$now$节点选了$p$门课所得最大收益 将$now$节点的每个子节点$v$看成一组物品,一组物品有$size[v]$个物品,每个物品的体积为$1$,选了$j$个物品的价值为$f[v][j]$ 于是这样写状态转移 12345for(ri i=m;i>=
题目链接https://www.luogu.org/problemnew/show/UVA1292 分析这不跟没有刘醒上司的舞会一样的套路么,怎么一个普及+,一个提高+.也是挺服luogu评分 $f[now][1/0]$表示取/不取$now$在$now$为根的子树中的最大值 转移照样简单 $f[now][0]=\sum max(f[son][0],f[son][1]) $,$son$是$now$的
题目链接https://www.luogu.org/problemnew/show/P1122 真 - 搜索剪枝题 分析这题也很好想,枚举每个节点与它儿子节点之间连的枝是剪还是不剪就好了 $f[now] = \sum max(f[son],0)$ 但这题有个需要注意的地方,就是你可能将一个节点与它父亲之间相连的枝条剪掉以获得最大答案,由于$f[now]$指在$now$为根的子树范围内的最大答案,所
题目链接https://www.luogu.org/problemnew/show/P1352 下属不允许啵上司嘴 分析经典的树形DP入门题,有了之前的经验很容易设计出状态,$f[now][1/0]$表示取/不取$now$节点并且以$now$的子树中的快乐总和最大值,显然这是一个最优子结构,根据题意状态转移方程也不难想出 $f[now][0]=\sum max(f[son][0],f[son
最近瞎搞用开源UOJ搭了个OJ,在题目配置方面搞了挺久,一开始看vfleaking的文档还折腾了SVN,特意写下这篇文章为后来人少走弯路 Step 1拥有管理权限并设置好题面,支持$LaTex$和Markdown Step 2 设置数据参考网站https://vfleaking.github.io/uoj/problem/ https://universaloj.github.io/post/%E
题目链接https://www.luogu.org/problemnew/show/CF340B $n$个点,找出能围成的四边形最大面积,$n<=300$ 分析这题像我这种菜鸡只会$O(N^4)$枚举啊,正解人太傻根本想不到 相比于朴素枚举,我们换个思路,先枚举对角线,再一遍$O(N)$枚举计算与对角线形成的三角形面积 我们用叉积计算所以有正有负,如果你会计算几何基础的话，那你肯定明白其实我