本文主要是介绍树上算法01-倍增LCA/Trie，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

树-相关算法

定义

• 任意两个节点之间只有唯一一条路径的无向图

• \(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);
   }

二叉/三叉链表

大家都会写

LCA算法

• 对于两个节点，首先其深度不同
• 移动一个节点直到二者深度相同
• 深度相同以后再向上寻找祖先
• 从距离最远的祖先开始跳，如果找到的祖先不相同就跳
• 最后停在LCA下面一层

倍增法

查找

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];
}

是谁把多叉树当二叉树做啊

是我啊

那没事了

DFS预处理

• DFS预处理，求出每个节点的不同级别祖先
• 记录深度

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）

trie树（存储字符串用于多模式串匹配）

存储实现

int node[lll][30];//记录节点儿子的编号

功能函数

• insert

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;
}

• find

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;
}

这篇关于树上算法01-倍增LCA/Trie的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！