lca与树上差分

lca与树上差分

const int maxn = 500010;
VI son[maxn];
int n, m, k, depth[maxn], fa[maxn][30], a, b, maxd;
void dfs(int x, int pre)//x表示当前dfs节点，pre为其父节点
{
    depth[x] = depth[pre] + 1;//计算x节点深度
    //maxd = max(maxd, depth[x]);
    fa[x][0] = pre;//向上走一步即为其父节点
    for (int i = 1; (1 << i) <= depth[x]; ++i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];//x向上走2^i步等同于x向上走2^i-1，再走2^i-1;
    for (int i = 0; i < son[x].size(); ++i) {
        if (son[x][i] != pre) dfs(son[x][i], x);//递归处理
    }
}
int up(int x, int d)//计算x向上走d步的节点
{
    int ret = x;//初始化
    for (int i = 26; i >= 0; --i)//考虑d的二进制表示为1的位置，用之前的处理向上跳跃
        if ((1 << i) & d)
            ret = fa[ret][i];
    return ret;
}
int lca(int x, int y) {//计算两个节点之间的lca
    if (depth[x] < depth[y])
        swap(x, y);//保证x深度较大
    x = up(x, depth[x] - depth[y]);
    if (x == y)
        return x;
    for (int i = 26; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];//如果跳2^i后不一样就跳上去
    return fa[x][0];
}
signed main()
{
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        son[a].push_back(b);
        son[b].push_back(a);
    }
    depth[0] = 0;
    dfs(k, 0);//k是根节点
    for (int i = 1; i <= m; ++i) {
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
    return 0;
}

树上差分

点差分

对树上的一些路径$(s_1,t_1),(s_2,t_2),(s_3,t_3)…$进行访问，问一条路径(s,t)上的点被访问的次数。 $\begin{aligned} &d_s\rightarrow d_s+1\\ &d_{lca}\rightarrow d_{lca}-1\\ &d_t\rightarrow d_t+1\\ &d_{f(lca)}\rightarrow d_{f(lca)}-1\\ \end{aligned}$

其中f(x)表示x的父亲节点，$d_i$为点权$a_i$的差分数组

边差分 $\begin{aligned} &d_s\rightarrow d_s+1\\ &d_t\rightarrow d_t+1\\ &d_{lca}\rightarrow d_{lca}-2\\ \end{aligned}$