树形背包优化
转：link 题意:给你一颗树,每个点有一个权值,每条边可以留下或删除,问有多少种方案使得1所在的连通块中所有点的权值和恰好为 KKK. 暴力 n3n^3n3: 123456789101112131415int dfs(int u, int fa) { sum[u] = val[u]; dp[u][val[u]] = 1; for (int i = head[u]; i; i = edges[i].nex) { int v = edges[i].to; if (v == fa) continue; dfs(v, u); sum[u] += sum[v]; for (int j = min(sum[u], K); j >= val[u]; --j) { dp[u][j] = 1ll * dp[u][j] * (1 + dp[v][0]) % mod; for (int k = max(1, val[v]); k...
tarjan缩点
强连通定义：在有向图 G{V,E}G\{V,E\}G{V,E} 中，对于点集 V′∈VV'\in VV′∈V , 点集中的任意两点都可达，则称 V′V'V′ 为强连通。 考虑建出图的 dfs 树，则原图上的边可以转换为三种边： 坑： 要写两个连边函数，把第二个函数的 siz 写成了 tot ，调了我一个晚上… 123456789101112131415void addline(int u, int v) { tot++; l[tot].from = u; l[tot].to = v; l[tot].next = hl[u]; hl[u] = tot;}void addedge(int u, int v) { siz++; e[siz].from = u; e[siz].to = v; e[siz].next = he[u]; he[u] = siz; //就是这里！} 由于存边的时候只存了一个点的后继节点，所以要根据节点...
换根dp
先看一个题目 CF161D Distance in Tree 考虑 dp（当然点分治也可以做），先求出 f(u,k)f(u,k)f(u,k) 表示将树中的 uuu 作为根节点后，深度为 kkk 的节点数量，则答案为 ∑u∈Gf(u,k)2\dfrac{\sum_{u\in G}f(u,k)}{2}2∑u∈Gf(u,k)。 可以暴力求 fff 数组，复杂度 O(n2k)O(n^2k)O(n2k)。 优化一下，先以 111 为根节点，求出从每个点 uuu 开始，向下走 kkk 的路径条数 g(u,k)g(u,k)g(u,k) 设节点 uuu 的一个儿子是 vvv 。观察到如果求出了 f(u,k)f(u,k)f(u,k) 那么求 f(v,k)f(v,k)f(v,k) 可以利用一下信息。 红色部分显然是 g(v,k)g(v,k)g(v,k) ，蓝色部分是 f(u,k−1)f(u,k-1)f(u,k−1)，但是这样有一部分会多计算，就是那些以 uuu 为端点，长度为 k−1k-1k−1 ，经过了红色部分的路径。减去 g(v,k−2)g(v,k-2)g(v,k−2)...
可持久化平衡树
link fhq 改几个函数就可以了 12345int refresh(int id) { tot++; p[tot] = p[id]; return tot;} 123456789101112131415void split_by_val(int rt, int &a, int &b, int val) { if (rt == 0) { a = b = 0; return; } if (p[rt].val <= val) { a = refresh(rt);// split_by_val(p[rt].rs, p[a].rs, b, val); pushup(a);//记得是pushup(a)，不是pushup(rt)！！！ } else { b = refresh(rt);// split_by_val(p[rt].ls, a,...
无旋Treap
参考：blog1 | blog2 定义一下变量： 123456789struct Node { int ls;//每个点的左儿子 int rs;//每个点的右儿子 int val;//每个点的权值 int rnd;//每个点的随机权值 int siz;//以每个点为根的树的大小} tree[MAXN];int root;//根节点编号int tot;//节点总数 主要有两个核心操作：split(int rt, int &a, int &b, int k) 和 merge(int a, int b, int &rt) ，分别表示将一颗 treap(rt)\mathsf{treap(rt)}treap(rt) 按权值分裂成两颗 treap(a)\mathsf{treap(a)}treap(a) 和 treap(b)\mathsf{treap(b)}treap(b) 以及将两颗 treap\mathsf{treap}treap 合并。 基本操作 分裂 split(int rt, int...