登录以参加训练计划

1，树的性质

• 1，对于有根树，除根结点外，其余结点有且仅有一个父结点。
• 2，n个结点的树有且仅有n-1条边。
• 3，树是不存在环的联通图。
• 4，树中任意两个结点之间有且仅有一条简单路径。

常见题型

1，计算每个结点的儿子个数：

给定一棵树中的若干父结点和子结点的关系描述（结点 1 是树根），请问该树中，每个结点有多少个子结点。

比如：读入父子关系如下，先读入父结点，再读入子结点。 1 2 2 3 2 4 读到一条边，通过cnt[x]++;统计个数，再输出即可。

当给出的的边并未明确谁是父结点，谁是子结点时，先分别对相应的结点儿子个数加1，最后，树中每个结点的儿子数等于与它相连的边数减1。因为在树结构中，每个结点的“儿子”（或称为子节点）是指直接连接到该结点的下一层结点。根结点是树的最顶层结点，没有父结点。对于除根结点外的任何结点来说，它通常有一个父结点和若干个子结点。当提到一个结点有一条边相连时，这条边要么是从父结点指向该结点，要么是从该结点指向其子结点。因此，除了根结点之外，每个结点都会有一条来自其父结点的边。 这意味着： 对于非根结点，它的边数等于它的儿子数加上一条来自父结点的边。因此，非根结点的儿子数等于与它相连的边数减去1（因为其中一条边是用来连接父结点的）。

关键代码： cnt[x]++,cnt[y]++; ... cnt[1]++//根结点要特殊处理一下。 ... cout<<cnt[i]-1<<endl;

2，树的存储与遍历方法

有根树的父亲表示法

除根结点外，其他结点有且只有一个父结点，因此，我们可以把每一条树边存储在其子结点上，记录形式为:i结点的父亲是 f[i] = j; 父亲表示法存储结构的实现代码如下：

int fa[N];
void link(int x,int y){
  fa[x] = y;//y是x的父亲
}//并查集也采用这样最基本的表示方法。

//并查集的find函数，带路径压缩。
int find(int x){
  if (fa[x] !=x){
    fa[x] = find(fa[x]);
  }
  return fa[x];
}

邻接矩阵

树也是一种特殊的图。因此数据量不大的情况下，可以用邻接矩阵来存。

int g[N][N];
...
g[x][y] = 1;//默认是0，有边相连为1，若是图还可以带权

邻接表（链式前向星）

树也是一种特殊的图，因此数据量大的情况可以用邻接表。

int h[N]//每个父结点的第一条边的索引
int ne[N]//下一条边的索引
int e[N]//当前边指向的子结点
int idx=1;//边的索引，
void add(int x,int y){//x是父亲，y是孩子
  e[idx]=y;//记录孩子的名字。
  ne[idx]=h[x];//新孩子拉住旧孩子的位置，相当于链表结构的头插法。
  h[x]=idx++;//父亲结点更新为新孩子的位置，然后再把idx加1.
}

int main(){
  add(5,3);
  add(5,7);
  //遍历5号父亲的所有孩子
  for(int i=h[5];i!=0;i=ne[i]){
    cout<<e[i]<<" ";//输出7 3添加顺序颠倒
  }
  return 0;
}

用vector 存

vector<vector<int>> g[N];
void add(int x,int y){
g[x].push_back(y);
}

树的深度优先遍历

有根树的深度优先遍历

int idx,h[N],e[2*N],ne[2*N];
void dfs(int x){
  visit(x);
  for(int i=h[x];i!=-1;i=ne[i]){
    dfs(e[i]);
  }
}

无根树的深度优先遍历

void dfs(int x,int y){
  visit(x);
  for(int i=h[x];i!=-1;i=ne[i]){
    if(e[i]!=y)
      dfs(e[i],x);
    
  }
}
dfs(root,-1);//一般把根结点设置为-1或者0

3，最近公共祖先

若两个点的祖先相同，则叫该点的公共祖先。距离两个结点最近的公共祖先称为最近公共祖先（Lowest Common Ancestor),简称LCA。显然，两个点的LCA只有一个，且一定是两个点到根的路径中重复部分最下端的点。

算法一：

void dfs(int x,int fath){遍历这棵树，并求出每个结点的深度和每个结点的父亲。
  fa[x] = fath;
  de[x] = de[fath]+1;
  for(int i=h[x];i!=-1;i=ne[i]){
    if (e[i] != fath) 
      dfs(e[i],x);
  }
  
}

int getLCA(int x,int y){
  while(x!=y){
    if (de[x]>=de[y]){
      x=fa[x];
    }else{
      y=fa[y];
    }//把深度较大的结点向上移。
  }
  return x;
}

树的重心

树的重心：指的是在树上的某个结点，如果以该结点为根，该结点所有子树结点数量的最大值中的最小值即为树的重心：

• 1，如果以某个结点为整棵数的重心，它的每棵子树的大小都<=n/2;
• 2，重心到其他点的距离和最小，如果有两个重心，他们的距离和一样。
• 3，一棵树添加或删除一个结点，树的重心至多只移动一条边的位置。
• 4，把两棵树通过某个点相连，得到一棵树，新的树的重心必然在连接两棵树重心的路径上。

线段树

线段树的原理：线段树除了最后一层之外，是一颗满二叉树，假设区间中存在n个数据，则倒数第二层节点数大于为n，从第一层到倒数第三层的节点数大约为n-1，最后一层节点数很少，但是为了使用数组存储整棵树，最后一层大约需要开2n的空间，因此一共需要开辟4n的空间存储线段树。

举例说明：

一个有 n 个元素的数组，构建出的线段树会有以下特点：

• 叶子层：有 n 个叶子节点，每个叶子节点对应数组中的一个元素。
• 倒数第二层：每个叶子节点都有一个父节点，这些父节点构成了倒数第二层。如果 n 是偶数，那么倒数第二层有 n/2 个节点；如果 n 是奇数，那么倒数第二层有 (n+1)/2 个节点。因此，倒数第二层的节点数至少为 n/2。

例子

假设有一个包含 7 个元素的数组 [a, b, c, d, e, f, g]，构建出的线段树如下所示：

            [0,6]
           /      \
     [0,3]        [4,6]
    /    \       /     \
[0,1]  [2,3]  [4,5]   [6,6]
 /  \   /  \   /  \     |
a    b c    d e    f    g

在这个例子中：

叶子层：有 7 个叶子节点，分别对应 a, b, c, d, e, f, g。

倒数第二层：有 4 个节点，分别是 [0,1], [2,3], [4,5], [6,6]。

可以看到，即使在 n = 7 的情况下，倒数第二层的节点数也是 4，超过了 n/2。这是因为当 n 是奇数时，最后一个区间 [6,6] 只有一个元素，但仍然需要一个节点来表示它。

为什么需要 4n 的空间？

叶子层：需要 n 个节点。

倒数第二层：至少需要 n/2 个节点。

上层节点：从根节点到倒数第三层，节点数大约是 n - 1（因为每层节点数逐渐减少，直到只剩下一个根节点）。

最后一层：虽然实际使用的节点可能很少，但我们为了方便使用数组存储整个线段树，通常会为最后一层预留足够的空间，即大约 2n 个节点。

因此，总的节点数大约是：

叶子层：n

倒数第二层：n/2

上层节点：n - 1

其它冗余节点：2n

加起来总的空间需求约为 4n。

通过这个例子和解释，我们可以理解为什么在最坏情况下，我们需要开辟 4n 的空间来存储线段树。这样可以确保无论数据如何分布，我们都有足够的空间来存储所有的节点。

线段树的基本操作

线段树是一种高效的数据结构，用于处理区间查询和更新操作。以下是线段树的几个基本操作及其说明：

1. pushup：由子节点计算父节点的信息

• 定义：pushup 操作用于从子节点的信息更新父节点的信息。
• 用途：在更新或构建线段树时，当子节点的信息发生变化后，需要调用 pushup 来更新父节点的信息。
• 示例：如果线段树用于区间求和，那么父节点的值将是两个子节点值的和。

2. pushdown：把当前父节点的修改信息下传到子节点（懒标记）

• 定义：pushdown 操作用于将父节点的修改信息传递给其子节点。这个操作也被称为懒标记或延迟标记。
• 用途：在区间修改操作中，为了避免不必要的更新，可以使用懒标记来延迟实际的更新操作，直到需要访问这些节点时再进行更新。
• 复杂性：这个操作相对复杂，通常只有在涉及区间修改时才需要实现。

3. build：将一段区间初始化成线段树

• 定义：build 操作用于构建线段树，将给定的一段区间初始化为线段树。
• 用途：在线段树的初始化阶段，通过递归地将区间分成更小的子区间，并构建相应的节点来完成整个线段树的构建。
• 示例：对于一个数组 [a, b, c, d, e, f, g]，build 操作会构建一个完整的线段树，其中每个节点代表一个区间的信息。

4. modify：修改操作

• 单点修改：
  • 定义：修改数组中的某个单个元素。
  • 用途：在更新数组中的某个元素后，需要调用 pushup 操作来更新相关的父节点。
• 区间修改：
  • 定义：修改数组中的一个区间内的所有元素。
  • 用途：在更新一个区间时，可以使用懒标记（pushdown）来延迟实际的更新操作，直到需要访问这些节点时再进行更新。

5. query：查询一段区间的值

• 定义：query 操作用于查询指定区间的信息。
• 用途：通过递归地访问相关节点，可以在 O(log n) 时间内完成区间查询。
• 示例：如果线段树用于区间求和，那么 query 操作可以返回指定区间的所有元素的总和。

总结

• pushup：由子节点计算父节点的信息。
• pushdown：把当前父节点的修改信息下传到子节点（懒标记）。
• build：将一段区间初始化成线段树。
• modify：修改操作，分为单点修改和区间修改。
• query：查询一段区间的值。

这些操作使得线段树能够高效地处理区间查询和更新问题，适用于多种应用场景。

建树

struct Node {
    int l, r;
    int v;
} tr[N * 4];

build:

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

pushup:

void pushup(int u) {
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

query:

int query(int u, int l, int r) {
    
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));
    return v;
}

modify:

void modify(int u, int x, int v) {
    
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}