树上差分

啊，训练时考了2015noip的day2，才突然发现自己不会树上差分。

那么现在就把这个知识漏洞补起来吧~>-<

我是从这篇文章学习的https://baijiahao.baidu.com/s?id=1615363433132223459&wfr=spider&for=pc

树上差分用于统计某个点或某条边被经过了多少次

树上差分有两种

1.点的差分

例如,我们从 s-->t ,求这条路径上的点被经过的次数.

很明显的,我们需要找到他们的LCA,(因为这个点是中转点)

我们需要让cnt[s]++,让cnt[t]++，而让他们的cnt[lca]--，cnt[faher(lca)]--

绿色的数字代表经过次数.

考虑：我们搜索到s,向上回溯.

下面以u表示当前节点,son_i代表i的儿子节点.(如果一些son不给出下标,即代表当前节点u的儿子

每个u统计它的子树大小,顺着路径标起来.(即cnt[u]+=cnt[son])

我们会发现第一次从s回溯到它们的LCA时候,cnt[LCA]+=cnt[son[LCA]]

cnt[LCA]=0! "不是LCA会被经过一次嘛,为什么是0!"

别急,我们继续搜另一边.

继续：我们搜索到t,向上回溯.

依旧统计每个u的子树大小cnt[u]+=cnt[son]

再度回到LCA 依旧是cnt[LCA]+=cnt[son[LCA]]

这个时候 cnt[LCA]=1 这就达到了我们要的效果

担忧：万一我们再从LCA向上回溯的时候使得其父亲节点的子树和为1怎么办?

这样我们不就使得其父亲节点被经过了一次? 因此我们需要在cnt[faher(lca)]--

这样就达到了标记我们路径上的点的要求

总结来说，就是在单点上进行修改，查某个点的经过次数时就统计此点的子树和

2.边的差分

我们对边进行差分需要把边塞给点,但是,这里的标记并不是同点差分一样.

PS: 把边塞给点的话,是塞给这条边所连的深度较深的节点. (即塞给儿子节点

红色边为需要经过的边,绿色的数字代表经过次数

正常的话,我们的图是这样的.↓

但是由于我们把边塞给了点,因此我们的图应该是这样的↓

但是根据我们点差分的标记方式来看的话显然是行不通的,

这样的话我们会经过father[LCA]--> LCA这一路径.

因此考虑如何标记我们的点,来达到经过红色边的情况

聪明的你一定想到了,这样来标记

cnt[s]++ ， cnt[t]++ ，cnt[LCA]-=2

这样回溯的话,我们即可只经过图中红色边。

同样的，统计某条边的经过次数只需要统计它的儿子节点的子树和

那让我们来看看有关的题目吧！

洛谷3128是一道很好的模板题（虽然名字是什么鬼扯的最大流）

#include<bits/stdc++.h>
#define N 50003
using namespace std;
int tot=0;
int head[N],to[N*2],nextt[N*2],dep[N],f[N][23],lala[N];
int read()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
void add(int x,int y)
{
    tot++;
    to[tot]=y;
    nextt[tot]=head[x];
    head[x]=tot;
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    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];
}
void dfs1(int x)
{
    for(int i=head[x];i;i=nextt[i])
    {
        int v=to[i];
        if(v==f[x][0]) continue;
        f[v][0]=x;
        dep[v]=dep[x]+1;
        for(int i=1;i<=20;++i) f[v][i]=f[f[v][i-1]][i-1];
        dfs1(v);
    }
}
int ans=-1;
void gao(int x)
{
    for(int i=head[x];i;i=nextt[i])
    {
        int v=to[i];
        if(v==f[x][0]) continue;
        gao(v);
        lala[x]+=lala[v];
    }
    ans=max(ans,lala[x]);
}
int n,k;
int main()
{
    n=read(),k=read();
    for(int i=1;i<n;++i)
    {
        int x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dep[1]=1;
    dfs1(1);
    for(int i=1;i<=k;++i)
    {
        int x=read(),y=read();
        lala[x]+=1;lala[y]+=1;
        int l=LCA(x,y);
        lala[l]--; 
        if(f[l][0]) lala[f[l][0]]--;
    }
    gao(1);
    printf("%d",ans);
}

洛谷3128

然后呢，就是2015noip day2的一道题运输计划

大概思路就是二分答案+倍增LAC+边的树上差分

在每次check答案的时候，对于不满足的链进行一个统计，再去找这些链中是否存在一条公共边，使得减去这条公共边后所有的链都满足条件

#include<bits/stdc++.h>
#define N 300005
using namespace std;
int a[N],b[N],l[N],to[N*2],head[N],nextt[N*2],valuee[N*2],vva[N],f[N][22],he[N],dep[N],p[N],dis[N],d[N];
int m,n;
int read()
{
    int x=0,f=1;
    char s=getchar();
    while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
int tot;
void add(int a,int b,int z)
{
    tot++;
    to[tot]=b;
    nextt[tot]=head[a];
    head[a]=tot;
    valuee[tot]=z;
}
int pp=0;
void dfs(int x,int ff)
{
    p[++pp]=x;
    for(int i=head[x];i;i=nextt[i])
    {
        int v=to[i];
        if(v==ff) continue;
        dis[v]=dis[x]+valuee[i];
        dep[v]=dep[x]+1;
        vva[v]=valuee[i];
        f[v][0]=x;
        for(int i=1;i<=20;i++) f[v][i]=f[f[v][i-1]][i-1];
        dfs(v,x);
    }
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    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];
}
int max1=0,maxx=0;
bool check(int mid)
{
    memset(he,0,sizeof(he));
    int cnt=0;
    for(int i=1;i<=m;++i)
    {
        if(d[i]>mid)
        {
            he[a[i]]++;he[b[i]]++;he[l[i]]-=2;
            cnt++;
        }
    }
    for(int i=n;i>=1;--i)
    {
        he[f[p[i]][0]]+=he[p[i]];
        if(vva[p[i]]>=maxx-mid&&he[p[i]]==cnt) return true;
    }
    return false;
}

int gao(int l,int r)
{
    int ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans; 
} 
int main()
{
//    freopen("transport.in","r",stdin);
//    freopen("transport.out","w",stdout);
    n=read(),m=read();
    int flagg=0;
    for(int i=1;i<n;++i)
    {
        int x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
        max1=max(max1,z);
    }
    dis[1]=0;
    dfs(1,1);
    for(int i=1;i<=m;++i)
    {
        a[i]=read(),b[i]=read();
        l[i]=LCA(a[i],b[i]);
        d[i]=dis[a[i]]+dis[b[i]]-2*dis[l[i]];
        maxx=max(maxx,d[i]);
    }
    printf("%d",gao(maxx-max1,maxx+1));
}
/*
6 3
1 2 1
2 3 4
3 4 6
4 5 2
5 6 7
1 3 
2 5
4 6
*/

运输计划

emmm，好像2016noip的天天爱跑步也是用树上差分解决，但我还没看rua~