任意两个节点之间只有唯一一条路径的无向图
\(n\)个节点,\(n - 1\)条边
//存储 struct edge{ int to; int pre; }e[ll]; //加边 void add(int x, int y){ e[++cnt].to = y; e[cnt].pre = last[x]; last[x] = cnt; } //遍历 for(int i = last[cur];i;i = e[i].pre){ if(e[i].to != fa)dfs(e[i].to,cur); }
大家都会写
int lca(int x,int y){ if(depth[x] > depth[y]){ int tmp; tmp = x; x = y; y = tmp; }//y is always deeper int two = 0; int d = depth[y] - depth[x]; while(d){ if(d%2)y = f[y][two]; ++two; d /= 2; } if(x == y) return y; //一起跳 for(int i = 20; i >= 0; --i){ if(f[x][i] != f[y][i]){ x = f[x][i]; y = f[y][i]; } } return f[x][0]; }
是谁把多叉树当二叉树做啊
是我啊
那没事了
void dfs(int cur,int fa){ depth[cur] = depth[fa] + 1; f[cur][0] = fa; for(int i = 1; (1<<i) < depth[cur]; ++i){ f[cur][i] = f[f[cur][i-1]][i - 1]; } for(int i = last[cur];i;i = e[i].pre){ if(e[i].to != fa)dfs(e[i].to,cur); } }
给出一个数组{\(a_i\)}
差分数组为{\(a_i - a_{i -1}\) }\((a_0 = 0)\)
便于对某一段区间进行统一的+n的操作,仅需改变区间头尾两个数字
查询原数组中某个数即求一段前缀和
\(def:fa = fa - ls - rs\)
支持对u到v路径上的所有点权值修改后,只需修改u、v、pla、pla ‘ s father四个点的值即可
所有修改结束以后将树还原
进行后续查询操作
dfs将每条边上的值放到下面的节点里
异或题:每个节点储存到根的异或值
询问路径长度
差分树:\(fa - (ls +rs)\)
DFS预处理:每个点记录到根的长度
\(Length_{uv} = l_u + l_v - 2l_{LCA}\)
三个点其实与两个点的没有太大差别,实在是弱搞得好复杂
可以用这个方法:\((1\rightarrow2+1\rightarrow3+2\rightarrow3)/2\)
如果把所有点两两跑一遍
\(length = a + b+a+c+a+d+b+c+b+d+c+d\)
\(length = 3(a+b+c+d)\)
再来看这棵树
\(length = a+b+a+b+c+a+d+c+b+d+c+b+d\)
??不符合条件
需要用到虚树相关知识(pks)
int node[lll][30];//记录节点儿子的编号
void insert(string s){ int root = 0; for(int i = s.length() - 1; i >= 0; --i){ int d = s[i] - 'a'; if(!node[root][d])node[root][d] = ++cnt; root = node[root][d]; } e[root] = true; }
bool find(string s){ int root = 0; for(int i = 0; i < s.length(); ++i){ int d = s[i] - 'a'; if(!node[root][d])return false; root = node[root][d]; } if(e[root])return true;//结束位置 return false; }