差分 | 0

就是前缀和嘿嘿

将 1 2 3 4 5 6 7 8 的2 和 6 中间的所有数标记一下标记

0 1 0 0 0 0 -1 0 求一下前缀和

0 1 1 1 1 1 0 0

树上差分

边差分： a->b cf[a]++,cf[b]++, cf[LCA]-=2;

点差分： a->b cf[a]++,cf[b]++, cf[LCA]--,cf[fa[LCA]]--;

例题：

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

View Code

代码

#include <bits/stdc++.h>
using namespace std;
const int M =100020;
const int N =50050;
#define ri register int
struct setbian{
    int net,to;
}bian[M];
int head[N],cent=1;
void add(int a, int b)
{
    bian[++cent].net=head[a],head[a]=cent;
    bian[cent].to=b;
}
int fa[N],dep[N],vis[N],ant[N][30];
void dfs1(int u,int f)
{
    vis[u]=1;
    dep[u]=dep[f]+1;
    for(ri i=1;(1<<i)<=dep[u];i++)
      ant[u][i]=ant[ant[u][i-1]][i-1];
    for(ri i=head[u];i;i=bian[i].net)
    {
        int v=bian[i].to;
        if(vis[v]==1) continue;
        ant[v][0]=u;
        dfs1(v,u);
    }
}
int LCA(int x,int y)
{
    if(dep[x]>dep[y]) swap(x,y);
    for(ri i=20;i>=0;i--)
    {
        if(dep[ant[y][i]]>=dep[x]) y=ant[y][i];
        if(y==x) return x;
        if(dep[x]==dep[y]) break;
    }
    for(ri i=20;i>=0;i--)
    {
        if(ant[y][i]!=ant[x][i])
          y=ant[y][i],x=ant[x][i];
    }
    return ant[x][0];
}
int n,m;
long long num[N];
long long ans;
void dfs2(int u,int f)
{
      vis[u]=1;
    for(ri i=head[u];i;i=bian[i].net)
    {
        int v=bian[i].to;
        if(vis[v]==1) continue;
        dfs2(v,u);
        num[u]+=num[v];
        ans=max(num[u],ans);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(ri i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    for(ri i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int c=LCA(a,b);
        num[a]++,num[b]++,num[c]--,num[ant[c][0]]--;
    }
    memset(vis,0,sizeof vis);
    dfs2(1,0);
    printf("%lld\n",ans);
}

View Code