题意： 给出一棵 n个节点的树，根节点为 1。每个节点上有一种颜色 ci。m次操作。操作有两种： 1 u c：将以 u为根的子树上的所有节点的颜色改为c。 2 u：询问以 u为根的子树上的所有节点的颜色数量。 题解：一看题目好像是个dfs序+线段树的板子题，但是需要思考的是，怎么查询一段区间的颜色数目呢？如果把这个问题解决了的话，这个题目也就相应的解决了。看到颜色数目好像并不多，嗷，极好，60（2^60）正好在ll的范围内。我们可以考虑每一位储存一种颜色，返回值为这段区间的(或)|。这样子dfs序建线段树跑一边即可。 /*Keep on going Never give up*/ //#pra...

题意:小A手头有 n 份任务，他可以以任意顺序完成这些任务，只有完成当前的任务后，他才能做下一个任务第 i 个任务需要花费 xi 的时间，同时完成第 i 个任务的时间不能晚于 yi，时间掌控者向小A提出了一个条件：如果完成第 i 个任务的时间本应是 t ，但小A支付 m 个金币的话，他可以帮助小A在 t − m × z 时刻完成第 i 个任务， zi​ 是时间参数，会在输入中给出小A想按时完成所有任务，请你帮他制定一个花费金币最少的方案注意：不能使得某个任务的花费时间小于 0 ,花费的金币可以不是整数： 题解：贪心我们首先按照结束时间对这些任务排个序，看看他在截至时间之间做完的话，超出多少...

题意：给你一棵n个结点的树, 以1为根。每个结点有点权。有m次操作：1.x结点权值 +val，x的儿子权值 −val，x的孙子们 +val，以此类推。2.询问x的点权；题解：我们首先跑一边dfs序，顺便求除每个结点的深度。我们把他分成两颗线段树，深度为奇数的在第一颗上，深度为偶数的在第二课上。我们每次对两颗线段树同时操作。第一颗线段树只进行＋操作，第二棵线段树只-操作。当我们询问某个点时，我们只需要判断一下这个点的奇偶，决定查询哪颗树即可。 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #i...

题意：已知有n个节点，有n−1条边，形成一个树的结构。给定一个根节点k，每个节点都有一个权值，节点i的权值为vi​。给m个操作，操作有两种类型：1 a x ：表示将节点a的权值加上x2 a ：表示求a节点的子树上所有节点的和（包括a节点本身）题解：dfs序+线段树用dfs序确定in[x]和out[x]的位置，in是当前结点开始的时间戳，out是回溯到当前结点的时间戳，当查询某结点时，可以快速确定他子树的范围。代码： /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include<bit...

题意：给定一个以1为根的n个节点的树，每个点上有一个字母(a-z)，每个点的深度定义为该节点到1号节点路径上的点数.每次询问 a,b 查询以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串.题解：dfs序+状态压缩+二分查找这个题用到了很多小技巧，比如说异或前缀和等等。我们首先对他跑一边dfs序，记录下每个点的时间戳。把每个层点入度的时间戳放在一起，因为结点到某层，也要保证这一层是他的孩子。所以我们用这个时间戳来确定到底是这一层的哪一段。用二分查找分别找入度结点和出度结点，从而确定范围。字母一共只有26个，于是考虑状态压缩。再对每层开一个vector维护前缀状态。再用异或前缀和...

题意：有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。 题解：要满足根节点的值最小，左子树的值大于右子树的值。这样的话我们可以先按照根->右->左的顺序来求出一个dfs序然后求一下LIS即可。 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #de...

题意：给你一棵树，有q次查询，每次查询第n个结点的他的子树按照dfs序第x个元素是什么？ 题解：一道dfs序的裸的题目。 首先需要一个数组存放第i个结点在dfs序中的位置再需要一个数组来存放dfs序的顺序在需要一个数组来存放一个结点子树的大小。（用来判断是否需要输出-1） 每次查询首先判断他的子树大小是否符合要求如果符合要求再找到这个结点在dfs序中的位置。然后利用存放dfs序顺序的数组瞬移 k-1 位，输出此元素即可。利用这三个数组，即可再O(n)的时间复杂度下解决问题。 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"O...

题解：欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次 问你走完这树上所有的点最短路径是什么。因为树是没有环的，所以你走到叶子结点的时候需要往回走，也就是再走一遍刚刚走过的路。 所以我们确定一条主道路，遇到分支就走一遍（主道路是不需要走两遍的）。因为所有长度都是已知的，所以最短路径也就是尽量让这一条主路变长。想一想最长的一条主路，那不就是树的直径吗。用所有路径长度*2-树的直径即为答案。两次dfs求树的直径 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #...

题意：给你n个数，每个数有一个值。问你这n个数的最小生成树为多少，两点之间的边权为异或值。 题解：参考了洛谷上的一个题解，总觉得这样的时间复杂度会爆炸，但是确确实实没爆炸。我们每次去合并两个点，要想尽量使全值小，对于一颗字典树来说，就要尽量先合并越靠树叶的结点，一个叶子结点对应一个结点。那么我们对于一颗字典树来说，我们把他运用到最近公共祖先上，把所有最近公共祖先的结点来说，他有两个孩子，也就是要练的结点就是所有的最近公共祖先的结点。对于每一个公共祖先结点，我们对其左右儿子尽心递归查找，尽量找到最小结点的值！ 也就是说对于某个结点，他拥有左右节点，无法避免的是让答案加上这一深度的值，但是对于左孩...

题意：第一行给你一个n第二行给你n个数字 分别是a[1],a[2].....a[n]。第三行给你n个数字 分别是b[1],b[2].....b[n]。 问：第三行的序列可自由排列，要求排列之后的顺序 a[1]^b[1],a[2]^b[2]...a[n]^b[n]的字典序最小。 题解：因为b数组可以自由排列，那么我们把b数组先生成一个字典序。要想字典序最小，那么根据贪心的思想，我们a[1]要与b中的某个数异或后值最小。那么我们再遍历一遍a数组每次找出当前能组合的最小值。 因为每次组合后，我们需要删除b中一个元素，那么b已经是字典树了，怎么删？我们用一个size数组来记录这个数出现的次数，和一个...

题意：给定一组数，然后对所有的数进行异或操作m次异或操作，问你每次操作后，没有出现过的最小的非负整数 题解：首先需要一个性质（a^b）^c=a^(b^c);所以我们没有必要对于所有的数进行异或操作。我们只需要设一个ans=0，每次用输入进来的数于ans进行异或即可。 其次，我们把没有出现过的数字加入进字典树，这样的话我们从高位到低位寻找与当前ans按位 比较相同的数字，如果不相同那么我们就给 返回值加上当前位的值。最后返回值极为最小mex。 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #...

题意：让你找一个连续区间异或和最大，如果有相同的，则输出断点较小的。 题解：01字典树，利用前缀和的思想进行求解，我们在插入前缀的同时，也在不断的更新最大值。我们查询当前 二进制字符串与已经插入的 二进制字符串中的哪一个异或和最大？找到最大的那个，读取这个前缀和是到谁结束的，来判断是否要更新 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> //#define int long long #define endl '\n' #def...

题意：给你一堆数，问你从里面跳出来两个数异或和最大。（菜鸡第一次用字典树做题）题解：之前没用过字典树做题，，看了大佬的题解，才知道字典树还有这种妙用。对于二进制，如果我们想让它最大，（一点贪心的小思想）那么最高位的1 我们是要尽量保留的，（再就是保留次高位.....）。对此我们建立一颗字01字典树，一条链对应的是一棵树的二进制形式，每次查询一个数字与已经放进去的最大异或值， 如何异或最大，就是在二进制下 与查询的这个数字 每位尽可能不同 ****当然前提下是从 最高位到最低位进行遍历（最高位权重大）。 所以根节点的两个孩子代表的是最高位的二进制数是几 代码： /*Keep on goi...

题意：模板题，求图中每个割点能把网络分成几个点双连通分量（不是割点就输出他有几块即可）。 题解：跟POJ 的SPF很像 这题用Tarjan来求，首先我们需要统计出来具体有几个连通块。对于每个连通块，我们需要判断这个割点去掉后，这幅图会被分成几块？这个其实很简单，只需要更改一下判断这个点是否为割点即可。每被判断成一个割点，那么这个割点++。注意特判根节点！ 看看它有几个不相连的子树 num[]代表的是 从这个点分支出去，有几个不相连的子树 到最后的时候要进行num[i]--，是因为他是头节点。（画个图理解一下） num[i]--;/*Keep on going Never give up*...