学习 一个算法 记忆，背过 多少有点 不是很自然， 算法中那些真正吸引人的地方是作者的设计思路，为了什么目的而设计成这样，觉得朴素的算法哪一步是不是占了点时间，我是不是能改进一下？（猜想） 之后通过自己精心设计一番努力， 改进成功，巨大的成就感，

你学牛顿力学的时候，能体会到牛顿被苹果砸的 疑惑过程和思考与窃喜吗？

正文

我们都学过线段树（没学过的同学知道 ###那是一个支持区间修改与区间查询的数据结构就行），是对一段序列进行维护，诶，那我们能不能拓展啊，，

就像 KMP 到 AC自动机 单独的一段序列 到树型结构

好，今天的问题就出现了，， 树上区间修改和区间查询，

不过，，树的区间似乎不太好定义，， 但是树有个特点啊，给定树中两点，这两点间的最短路径是唯一确定的

也很好理解啊，，如果树中两点间的路径有两条的话，就会出现环，

那么我们的树型结构的类比序列的区间 就是 两点间的路径，

再一点，给定一个点，这个点的子树就确定了，那么这个子树的所有节点，也可以看作“区间”

今天要解决的问题就是树 上 对这些区间进行修改，，对这些区间进行查询，

1. 给树种两点间的路径上的点全部加上一个值，

正常思维，，这两点间的路径就是 这两点到他们的最近公共祖先的路径并起来，先求一波lca，然后dfs（lca）

那个儿子节点的子树中有这两个点其中之一，就这个点加权值，

这种做法， 如果这两个点的路径长度为len的话，要进行len次修改，，很低效，

线段树不也是把区间修改从 一个个单点修改，，搞成 某些点合并成一个段， 就只去修改段，从而提高了效率的吗

树中的路径，我们能不能也把某些点合并，从而只去加这个段，

先上一个图，空说可能会有点抽象

这里的红边就是我们的连成段的地方

这些红边是有特点的啊，，

1.这些红边不会出现人字形 ###也好理解，，树中的路径都是往上走的，也不会出现人字形，所以我们要连的段也不应该有人字形，（段，是将来要整#体加的）

2.在1的条件下，我们就已经能搞出 这个红边的创造方法了， 每个节点 向它的儿子节点 其中之一 连红边

我是把红边看成是 城市间修路 修了路的话，父节点到那个修路的子节点 对这条路进行修改 查询 什么的就会很快，而其它没有修路的儿子节点，则要花费较大一点的代价，因为没有路，就不是很顺畅，如果也要经过的话需要更多的付出

好， 每一个节点都可以且只可以给它的一个儿子，，开条小道，

这条小道开给谁呢？， 伟大的父亲还是公平公正的，他要考虑开完路后整体的花费尽量小，

他发现 开完路后，他到开路的那个子节点的子树中点的路径就会相比其它他的没有开路的儿子的 会快一步

开路方法已经有了轮廓了，儿子节点中谁的子树size大就开给谁， 因为之后可能会到达这个子树中所有的点，只能快一颗子树中的点的话，那么，我们肯定希望开完路后变快的点 会多一些，，这样，整体这颗子树的每一条自上而下的路 平均一下 快的程度 相比给size第二大的儿子开路的做法 会更多

再看这张图

这些红边的 用法就是 红边中的点找父亲节点的时候，直接跳到 红边的顶部 孤立的点也可以看作0条边但是有一个点的红边

下面具体讲这些红边怎么用

问题会先给出来，给定两个点，两点间路径要全部加一个值

首先得找到最近公共祖先lca，， 往上找的过程中，红边可以看成一次直接到达红边顶部，非红边 则一次只能上升一个深度，

很明显，已经在上面的点应该等一等， 让下面的点也就是深度更大的点先往上走， 两点间， 深度大的点每上升一次，就看一下 两个点的所在红边的顶部是否相同， 相同则走到了lca 寻路完成

从红边中的点直接跳到红边顶部 对应线段树中的区间

搞个最简单的只有加的线段树就能实现

这就需要我们 让，然后红边中的点编号连续，

为达成这个目的，先dfs一遍 找出每个点（u）的 儿子节点中size最大的哪一个，称为 son[u];

然后第二遍dfs 搜到u的时候 优先搜索son[u]，这样 红边中的点的编号就连续了，

void dfs1(int u, int father, int depth)
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int t)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/521494/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

学算法的时候要是有人讲这些 思路与精心设计， 多好，，

背过，会用，就行，感觉学起来会有点，，不是很舒服，

好比，谈恋爱，， 诶，跟着感觉走就挺好啊，
要是恋爱有本教科书 ，教科书上说什么你就在恋爱中做什么，，那你这恋爱有什么意义呢，

背—————— 会很枯燥，，探索—————— 会爽的一p

你学牛顿力学的时候，能体会到牛顿被苹果砸的 疑惑过程和思考与窃喜吗？