思路： 1.询问一个节点的共有多少个不同的名字，可以用类型的数组来存子树某个深度某个名字出现的次数，来记录子树某个深度有多少个不同名字的节点2.将每次查询用容器存储，方便离线操作3.题目给的是森林，需要存每颗树的根节点复杂度： MyCode: #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7,maxm=1e5+7; typedef long long ll; inline ll read(){ ll s = 0, w = 1; char ch = getchar(); while (ch < 4...

思路： 1.询问一个点与多少个点拥有共同的级祖先，可以理解为一个点的级祖先有多少个级儿子即有多少深度为的孩子，最后答案别忘了 ，因为把自己也算了在内2.求出相关的点的级祖先可以用求的倍增法3.将每次查询用容器存储，方便离线操作4.题目给的是森林，需要存每颗树的根节点复杂度： MyCode: #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7,maxm=1e5+7; typedef long long ll; inline ll read(){ ll s = 0, w = 1; char ch = get...

思路： 1.要能形成回文串，所以最多只能有一种字母的出现次数为奇数2.用一个数组存每个深度每个字母出现的次数3.查询以 为根的子树内深度为 的节点上的字母重新排列之后是否能构成回文串只要另外判断深度为的节点上是否只有一种字母的出现次数为奇数4.为了方便离线查询，用容器存每次查询，存节点是第次询问以及查询的深度的复杂度： 复杂度证明：1.一个点只有在它到根节点的路径上遇到一条轻边的时候，自己的信息才会被祖先节点暴力统计一遍2.而根据树链剖分相关理论，每个点到根的路径上有 条轻边和 条重链3.即一个点的信息只会上传次4.如果一个点的信息修改是 的，那么总复杂度就是的 MyCode: #includ...

借鉴博客：【学习笔记】树上启发式合并 / DSU on Tree树上启发式合并dsu on tree学习笔记  思路： 暴力：复杂度对于每个节点，暴力遍历子树，将它们的数据统计出来得到当前节点的答案，然后再暴力将这棵子树的数据清空，以免影响到别的节点。首先考虑为什么要把子树的数据清空（会占用很多时间）：对于节点 ，在做子树答案时是相互独立的，由于空间的限制，我们不可能对于每一个节点开一个数组来记录数据，只能开一个全局数组。所以在做下一个结点的答案时，如果上个结点的数据没有清空会导致结果出错。但是我们发现只是子树的结果互相影响，而做节点 为根的树的答案是要用到子树的数据的，所以最后一个子树的数据...

题意：给出一个，求有多少对素数相加等于 思路：打个素数表就很简单了，注意一个细节，数组一个字节，可以开，四个字节，在这题如果开会超内存，而且以内只有个素数。 MyCode： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e7+7,maxm=1e6+7; bool vis[maxn]; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) ...

题意：给你一些数，对于每一个求出数且的欧拉函数的值不小于，并且是所有的N的和加起来最小。 欧拉函数板子题。 MyCode: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+7; int prime[maxn],vis[maxn],phi[maxn]; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-'...

题意：数字满足的条件是该数字可以被它的每一位非零位整除。 思路： 数位dp的核心思路就是找到判断这个数的满足条件的方法，这个题的条件就是这个数要能被自己的每一个非零位整除，也就是应该被每一非零位的最小公倍数整除，而的最小公倍数是，现在就可以拟确定dfs的参数和dp的状态了。 ，表示当前处理到第位，表示当前数值的值，表示当前的最小公倍数，表示当前是否有范围限制。 临界点也是最重要的部分，当时，返回。 数位dp的状态就应该是，即位数符合条件的数的个数，但和最大都是，也就是说数位要开，开不了这么大。但一维里面的很多空间是多余的，因为的最小公倍数有种，所以将离散化到的区间，这样就可以开的数组了。 My...

思路： 区间内找出不含7的个数以及区间这些数的和都是数位的板子题，求区间内不含7的数的平方和需要推导公式。数位求位数的结果时，是将位数的结果相加得到的。 这不像我们平时写的那些数位题只求满足条件的数的个数，所以我们可以考虑设成结构体数组，存符合条件的个数，存符合条件的数的和，存符合条件的数的平方和。 ,表示满足条件的位数的结果。 最高位到第位的位数和的值为，最高位到第位的数值和的值为 设，作用相当于：123，第3位是1，那么 那么， 是存某个位数结果的结构体（第位是），是存ans后面某个位结果的结构体。 ,于是可以求位数符合条件的数的平方和已经存过了，即需要注意的是，是包含多个数的，包含个符合...

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3 + 7; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s ...

模板

poj3384  #include<bits/stdc++.h> using namespace std; const int maxn=1e5+7,maxm=2e5+7; typedef long long ll; inline ll read(){ ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s &lt...

hdu 3394 题意：有一个公园有n个景点，公园的管理员准备修建m条道路，并且把参观路线安排成回路。如果一条道路被多条参观路线（也就是这个点连通分量含多个环）公用，那么这些参观路线中会有冲突；如果一条道路没在任何一个回路内（这个道路就是桥），那么这条路是不冲突的。问分别有多少条有没有冲突的路和有冲突的路（从例子里看含多个环的点双连通分量的全部边都是有冲突的）。思路：要形成环是求点的双连通分量，这样才满足只有一个环的双连通分量中的边数等于点数。在点双连通分量中：当点数=边数，形成一个环当点数>边数（一条线段，说明这条边是桥）当点数<边数，那么就含1个以上的环了特殊情况，假设只有一条...

1.割点、割边 都是在深度优先生成树的基础上 判断割点：low[v]>=num[u]&&u!=1low[v]>=num[u]\&\&u!=1low[v]>=num[u]&&u!=1或者顶点（将1设为顶点）有两个或两个以上孩子 判断割边：low[v]>num[u]&&u!=1low[v]>num[u]\&\&u!=1low[v]>num[u]&&u!=1或者顶点（将1设为顶点）的孩子v有个兄弟 以下代码将low[v]>=num[u]&&u!=1...

一.Treap树 左旋和右旋右旋：  左旋：  旋转代码，son[0]是左儿子，son[1]是右儿子 void rotate(Node * &o,int d){ //d=0,左旋转；d=1，右旋转 Node *k=o->son[d^1]; //d^1与1-d等价 o->son[d^1]=k->son[d]; //相当于途中的between E and S k->son[d]=o; o=k; //返回新的根 } Treap树的删除如果待删除的结点是叶子结点，直接删除就好了。如果待删除的结点x有两个子结点，那么找到优先级最大的一个子结点，把x向相反的反向旋转，也就是...