树上差分

1.点差分：

求解问题：

给一棵树，和一些路径的起点和终点，求树上的每个点被路径经过的次数。

求解步骤：

  1.假设路径的起点： $s$s ，终点： $t$t， $a=lca(s,t)$a=lca(s,t) ， $fa\left[a\right]$fa[a] 为 $a$a 的父亲节点, $pum\left[x\right]$pum[x] 为每个点别路径的经过次数，那么对于每条所给的路径，进行下列操作：

$pum\left[s\right]++;\hspace{0.25em} pum\left[t\right]++;\hspace{0.25em} pum\left[a\right]--;\hspace{0.25em} pum\left[fa\right[a\left]\right]--;$pum[s]++;pum[t]++;pum[a]−−;pum[fa[a]]−−;
复杂度： $O\left(logn\right)$O(logn)

  2.对树用 $dfs$dfs 求一遍前缀和，回溯的时候计数，即可求出各个点的经过次数（或最大值）,复杂度 $O\left(n\right)$O(n)。

理解：

  两点的lca一定在两点的最短路径上，从两个端点向lca各自求前缀和时，路径上的点的值就相应增加。 $pum\left[a\right]--$pum[a]−− 是因为两个端点各自重复记了一次。 $pum\left[fa\right[a\left]\right]--$pum[fa[a]]−− 防止 $fa\left[a\right]$fa[a] 的次数改变。

例题：

P3128 [USACO15DEC]最大流Max Flow 【模板】

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
const int mak=20;
vector<int>pic[N];
int pre[mak][N],depth[N],pum[N];
int ans;
void dfs(int v,int p,int d)
{
    depth[v]=d;
    pre[0][v]=p;
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u!=p)
            dfs(u,v,d+1);
    }
}
void dfs2(int v,int p)
{
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u!=p)
        {
            dfs2(u,v);
            pum[v]+=pum[u];
        }
    }
    ans=max(ans,pum[v]);
}
void init(int n)
{
    dfs(1,1,0);
    for(int k=0;k+1<mak;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(pre[k][i]==-1)
                pre[k+1][i]=-1;
            else
                pre[k+1][i]=pre[k][pre[k][i]];
        }
    }
}
int lca(int u,int v)
{
    if(depth[u]>depth[v])
        swap(v,u);
    for(int k=0;k<mak;k++)
    {
        if((depth[v]-depth[u])>>k&1)
            v=pre[k][v];
    }
    if(u==v)
        return u;
    for(int k=mak-1;k>=0;k--)
    {
        if(pre[k][u]!=pre[k][v])
        {
            u=pre[k][u];
            v=pre[k][v];
        }
    }
    return pre[0][u];
}
int main()
{
    int n,k,u,v,s,t;
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        pic[u].push_back(v);
        pic[v].push_back(u);
    }
    init(n);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&s,&t);
        int an=lca(s,t);
        pum[s]++;
        pum[t]++;
        pum[an]--;
        pum[pre[0][an]]--;
    }
    ans=0;
    dfs2(1,1);
    printf("%d\n",ans);
    return 0;
}

2.边差分：

例题：

P2680 运输计划