爱飞鱼的blog

时间复杂度 O(nm2)O(nm^2)O(nm2)，理论上限 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859//n,m,s,t，分别代表该网络的点数n，网络的边数m，源点编号s，汇点编号t。const int N=5010,M=100010,INF=1e8;int n,m,S,T;struct edge{int v,c,w,ne;}e[M];int h[N],idx=1;//从2,3开始配对int d[N],mf[N],pre[N],vis[N];int flow,cost;void add(int a,int b,int c,int d){ e[++idx]={b,c,d,h[a]}; h[a]=idx;}bool spfa(){ memset(d,0x3f,sizeof d); memset(mf,0,sizeof mf); ...

从启发式合并到Dsu on Tree 传统启发式合并 [HNOI2009] 梦幻布丁 题目描述 nnn 个布丁摆成一行，进行 mmm 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 1,2,2,11,2,2,11,2,2,1 的四个布丁一共有 333 段颜色. 输入格式 第一行是两个整数，分别表示布丁个数 nnn 和操作次数 mmm。 第二行有 nnn 个整数，第 iii 个整数表示第 iii 个布丁的颜色 aia_iai​。 接下来 mmm 行，每行描述一次操作。每行首先有一个整数 opopop 表示操作类型： 若 op=1op = 1op=1，则后有两个整数 x,yx, yx,y，表示将颜色 xxx 的布丁全部变成颜色 yyy。 若 op=2op =...

https://www.acwing.com/problem/content/description/2071/ 每次合并的时候需要开一个新点去实现信息的无后效性，也就是合并之前的两个连通块信息是无法共享的，发现这样开点连边最后 形成一棵树，每次我们将信息传递到新点，也是两个合并点的lca，这使得最后求答案的直接求一边树上前缀和，不同子树不受影响 debug：最后合并n-1次，初始化和空间都要开两倍 // Problem: 网络分析 // Contest: AcWing // URL: https://www.acwing.com/problem/content/2071/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define ll long long //# define int long long #define...

一类以并查集在建树过程中维护各种信息的值——克鲁斯卡尔重构树前身 第一次见到是在zzu的校赛中，印象深刻。 H. Sum of Maximum Weights 题意 给定一棵树，求树上任意两点间最短路径中的最大边权的和。 官方 Solution 将边按权值排序，每次处理当前的最大权值。 处理每条边时，由于树的性质，边的起点和终点一定连通。设两个组 UUU 和 VVV，则 UUU 组中任意成员到 VVV 组中任意成员的最大路径边权必为当前边的权值 eee，故可以写出 ans+=siz[u]×siz[v]×eans += siz[u] \times siz[v] \times eans+=siz[u]×siz[v]×e。 将两组合并，重复上述过程，最终得到答案。 我的理解 如果了解克鲁斯卡尔重构树，这就是一道板子题。 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <bits/stdc++.h>#define int long...

给定一棵有 nnn 个点的树，询问树上距离为 kkk 的点对是否存在。 第一行两个数 n,mn,mn,m,n个点。 第 222 到第 nnn 行，每行三个整数 u,v,wu, v, wu,v,w，代表树上存在一条连接 uuu 和 vvv 边权为 www 的路径。 接下来 mmm 行，每行一个整数 kkk，代表一次询问。 对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。 对于 100%100\%100% 的数据，保证 1≤n≤1041 \leq n\leq 10^41≤n≤104，1≤m≤1001 \leq m\leq 1001≤m≤100，1≤k≤1071 \leq k \leq 10^71≤k≤107，1≤u,v≤n1 \leq u, v \leq n1≤u,v≤n，1≤w≤1041 \leq w \leq...

树哈希 一种好写且卡不掉的树哈希 考虑这样一种哈希方式。对于一棵以 𝑎为根的子树，假设儿子是v1,v2,⋯ ,vkv_1, v_2, \cdots, v_kv1​,v2​,⋯,vk​，定义子树的哈希 h(a)=1+∑1≤i≤kf(h(vi))h(a)=1+\sum_{1\le i\le k} f(h(v_i))h(a)=1+∑1≤i≤k​f(h(vi​))。其中h(vi)h(v_i)h(vi​) 是 viv_ivi​对应子树的哈希，fff 为一个待定函数。 可以证明：如果 fff 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 O(n2/2w)O(n^2/2^w)O(n2/2w)。只需考虑最深的一对冲突点即可。 上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。 实践中，我们并不能取一个真正的随机函数当 fff。但事实上，没有特殊性质的 fff 几乎都卡不掉；因为随便找个 fff 大概率很随机。 有一些反例：如果 fff 取多项式，可能因为一直保持 2k2^k2k...

已知一棵包含 NNN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上 zzz。 2 x y，表示求树从 xxx 到 yyy 结点最短路径上所有节点的值之和。 3 x z，表示将以 xxx 为根节点的子树内所有节点值都加上 zzz。 4 x 表示求以 xxx 为根节点的子树内所有节点值之和 输入格式 第一行包含 444 个正整数 N,M,R,PN,M,R,PN,M,R,P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含 NNN 个非负整数，分别依次表示各个节点上初始的数值。 接下来 N−1N-1N−1 行每行包含两个整数 x,yx,yx,y，表示点 xxx 和点 yyy 之间连有一条边（保证无环且连通）。 接下来 MMM 行每行包含若干个正整数，每行表示一个操作。 输出格式 输出包含若干行，分别依次表示每个操作 222 或操作 444 所得的结果（对 PPP 取模）。 对于 100%100\%100%...

从树形dp到树上背包 1.https://www.luogu.com.cn/problem/P1122给定一棵树，每个点有点权，可能为负，求最大权值联通块。 Sol：我们考虑以1为根。树定向后对于任意一个连通块来说，他的形态也一定是一棵树，我们考虑在它的根上会计算到他对答案的贡献。所以问题转化为：求以i为根的最大子树权值和。 对于这个问题我们直接进行dp即可。dp[i]表示在i的子树里面，包含i的联通块的最大权值和。转移就是dp[u]=a[u]+∑v∈son[u]max⁡(0,dp[v])dp[u]=a[u]+ \sum_{v \in son[u]} \max(0,dp[v])dp[u]=a[u]+∑v∈son[u]​max(0,dp[v]) 一个实现细节是：我们必须不能选择空集，所以我们需要保证我们的答案初始值足够小，是负无穷。 几乎一模一样的阅读理解题https://www.luogu.com.cn/problem/P5766 12345678910111213141516171819202122232425262728void solve() { ...

树上换根dp 换根dp: 换根dp往往需要处理去掉一个子树这样的问题，我们可以使用前后缀和的方法来优化复杂度 Problem - 543D -...

树上启发式合并（常常也叫DSU On Tree，但其实和DSU并没有特别大关系），是一种解决某些树上离线问题的算法，尤其常被用于解决“对每个节点，询问关于其子树的某些信息”这样的问题。 假设我们要对树上的每个节点p求ans[p] ，且这个ans[p] 可以通过合并p的子节点的某些信息得知，一般来说我们可以用树形DP解决。但如果“子节点的某些信息”的规模较大，简单的树形DP在时间和空间上都可能爆炸。所以我们不能存储每个节点的信息，而是要实现某种资源复用。 - 有一棵 nnn 个结点的以 111 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， iii 号结点的颜色编号为 cic_ici​。 如果一种颜色在以 xxx 为根的子树内出现次数最多，称其在以 xxx 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。 你的任务是对于每一个 i∈[1,n]i\in[1,n]i∈[1,n]，求出以 iii 为根的子树中，占主导地位的颜色的编号和。 n≤105,ci≤nn\le 10^5,c_i\le...