【每日一题】dfs序专题 11月9日-13日题目

Military Problem
选点
Tree Requests
Colorful Tree
求和
Propagating tree

题解

11月9日-11月13日更新以上题目题解~
温馨提醒：之前的每日一题当中有三个和本专题相关的题目，同学们可以先学习。
4月7日每日一题 树
7月8日每日一题 Alliances
8月20日每日一题 华华和月月种树

————————————以下是介绍以前介绍过的dfs序的分割线-————————————
dfs序：每个节点在dfs深度优先遍历中的进出栈的时间序列（为了方便接下来的操作我们往往有两种不同的写法，一种是只记录进栈顺序，一种是进栈出栈都记录，视题目的具体情况而定怎么写。）

一般来讲，我们需要的不仅仅有这个进出栈的顺序序列，还有每个点在第几个进栈这个信息——点x在第几个进栈就是这个点的时间戳，一般记为dfn[x] (时间戳在强连通分量tarjan算法里也有很巧妙的运用)。
正如图上所说，第二种dfs序两个相同数字之间就是这个点的子树，而其实在第一种方法中你也可以用个数组记录它出栈的之前最后一个进栈的点，也就是当前访问过的点里面时间戳最大的是哪一个，这样也可也得到这个点对应的子树是在哪一个区间里了。将来你就可以通过诸如在这个树上建线段树的操作实现对子树的一些修改的维护，比如说子树所有点的权值加一个数，就很美滋滋了（这个以后有机会再讲）。
稍微注意一点，在一般的树中（二叉树除外）一个节点的儿子是没有左右顺序的，可以随便先访问哪个，所以，一棵树的dfs序是可能有很多种的。

————————————————以下第一个题————————————————
NC112932 Military Problem
DFS序的模板题：在dfs序中一个子树是连续的一段，所以我们可以记录每个点x进入dfs序的位置s[x]和离开dfs序的位置t[x]，这两个位置之间的点就是这个点的子树中的点。
那么对于每个查询来说，首先判断t[v]和s[v]的差值是否大于等于k，如果不是说明没有那么多子孙，输出负一，如果有则输出dfs序的t[x]+k-1位即可。

————————————————以下第二个题————————————————
NC22494 选点
认真分析选点规则：选中的根节点比子孙小，同一棵子树左子树比右子树大。也就是说在一棵子树中，选中的根节点最小，右子树里面的点其次，左子树里面的点最大。那么如果我们对换左右子树遍历整棵树（即按照根-右-左的顺序遍历），最后选中的点一定排成一个上升的序列。所以问题就转化成了在这棵树的按照“根-右-左”遍历的dfs序里求最长上升子序列。

————————————————分割线啦啦啦————————————————
NC111044 Tree Requests
好像大家都用dsu？其实更基础的知识同样能做这个题，虽然能抓到耗子的就是好猫，dsu实质上也就是个稍微优化了一下的暴力，但是这里想借机和大家说：不要过于迷信高级数据结构和边缘知识点哦！
我们来看看dfs序的解法：
首先我们知道一些字符能够成一个回文串的条件是:最多只有一个字母出现奇数次。也就是说我们需要再每次查询的时候知道当前这个子树的这一层每个字符出现的次数。
那么我们在dfs的时候就用一个vector记录每一层每一个字母的时间戳（在dfs序里出现的位置），每次查询x点的第y层子孙的时候，只需要到第y层的每个字符的vector里查询有多少个点的时间戳在进入x点之后且再从x点出去之前（即记录进入x的位置和离开x的位置，在vector里面二分查找这两个位置看中间有多少个点），然后判断个数奇偶即可。

———————————————我是下一个题的分割线———————————————
NC204871 求和
子树在dfs序中是一个区间，所以可以用dfs序把树上问题转化到区间里。问题变成单点修改区间求和，用树状数组即可。

————————————————好短，下一个————————————————
NC110318 Propagating tree
儿子和孙子操作不一样，但是“隔代”的操作是一样的，所以把dfs序按照每个点是在奇数层还是偶数层分成两个序列，建两棵线段树/树状数组，然后就是正常的区间修改和单点查询了。

———————————————快结束了————————————————
NC200179 Colorful Tree
我们来从特殊情况开始讨论：
如果颜色为y点的点只有1个——生成树大小为1；
如果颜色为y点的点有2个——生成树大小就是这两个点在树上的距离；
如果颜色为y点的点有3个——考虑先把两个点连起来（即2个点的情况），然后把第三个点x加进来，此时我们需要计算当前这个点加进来时对答案的影响——增加(dis(x,u)+dis(x,v)-dis(u,v))/2，uv就是之前已经算过的两个点。

之后每增加一个点，这个点也会增加(dis(x,u)+dis(x,v)-dis(u,v))/2，uv是与他相邻的两个点（如果左右都有就是一左一右，如果只有一边有就是这一侧离它最近的两个）

所以我们需要对每个颜色的点都按照其dfs序来维护（需要插入和删除操作，所以需要用set）每次插入/删除的时候把相邻两个点拿出来计算他的贡献即可。
（两个点的距离用深度和LCA求）
————————————————完结撒花————————————————

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

11月20日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴