【2019.7.10】树上差分杂[LCA 倍增][树上差分点差分边差分]-蒲公英云

多用于记录树上节点被经过的次数,记录某条边被经过的次数的时候

点差分

P3128 [USACO15DEC]最大流Max Flow

s−−>t求这条路径上的点被经过的次数找到他们的LCA 需要让 cnts++ cntt++ cntlca-- cntfa(lca)--

/*
 id:lxyyyy
 树上差分 3128 
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
#define lson o<<1
#define rson o<<1|1
const int N=50000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,k,cnt[N],f[N][25],dep[N],ans=0;
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}
int head[N],tot=0;
struct edge{
      int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++tot]=(edge){v,head[u]};head[u]=tot;
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=20;++i){
        if(dep[u]<(1<<i)) break;
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa) continue;
        dfs(e[i].v,u);
    }
}
int LCA(int a,int b){
    if(dep[a]>dep[b]) swap(a,b);
    for(int i=20;i>=0;--i){
        if(dep[f[b][i]]<dep[a]) continue;
        b=f[b][i];
    }
    if(b==a) return a;
    for(int i=20;i>=0;--i){
        if(f[a][i]==f[b][i]) continue;
        a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}
void dfs2(int u,int fa){
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].v;
        if(v==fa) continue;
        dfs2(v,u);
        cnt[u]+=cnt[v];
    }
}
int main(){
    rd(n),rd(k);
    for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v),add(v,u);
    int s,t;
    dfs(1,0);
    while(k--){
        rd(s),rd(t);
        int lca=LCA(s,t);
        ++cnt[s],++cnt[t],--cnt[lca],--cnt[f[lca][0]];
    }
    dfs2(1,0);
    for(int i=1;i<=n;++i) ans=max(ans,cnt[i]);
    printf("%d",ans);
    return 0;
}

最大流点差分

P3258 [JLOI2014]松鼠的新家

要注意它从顺序上2~n-1个点都重复走了一次而最终到最后一个点时它不用算一次所以将顺序上2~n的点的次数依次减一

/*
 id:lxyyyy
 树上差分 3128 
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
#define lson o<<1
#define rson o<<1|1
const int N=300000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,a[N],cnt[N],f[N][25],dep[N],ans=0;
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}
int head[N],tot=0;
struct edge{
      int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++tot]=(edge){v,head[u]};head[u]=tot;
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=20;++i){
        if(dep[u]<(1<<i)) break;
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa) continue;
        dfs(e[i].v,u);
    }
}
int LCA(int a,int b){
    if(dep[a]>dep[b]) swap(a,b);
    for(int i=20;i>=0;--i){
        if(dep[f[b][i]]<dep[a]) continue;
        b=f[b][i];
    }
    if(a==b) return a;
    for(int i=20;i>=0;--i){
        if(f[b][i]==f[a][i]) continue;
        a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}
void dfs2(int u,int fa){
    for(int i=head[u],v;i;i=e[i].nxt){
        v=e[i].v;
        if(v==fa) continue;
        dfs2(v,u);
        cnt[u]+=cnt[v];
    }
}
int main(){
    rd(n);
    for(int i=1;i<=n;++i) rd(a[i]);
    for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v),add(v,u);
    dfs(1,0);
    for(int i=2;i<=n;++i){
        int lca=LCA(a[i-1],a[i]);
        ++cnt[a[i-1]],++cnt[a[i]],--cnt[lca],--cnt[f[lca][0]];
    }
    dfs2(1,0);
    for(int i=2;i<=n;++i) --cnt[a[i]];
    for(int i=1;i<=n;++i) printf("%d\n",cnt[i]);
    return 0;
}

松鼠的新家点差分

边差分

用cf[i]表示i点到它父亲的这条边关于边的差分lca不包括在里面所以考虑u->lca这条链则使cf[u]++ cf[lca]—

同理lca->v cf[v]++ cf[lca]— 则总的为cf[u]++ cf[v]++ cf[lca]-2

POJ 3417loj暗的连锁

主边构成树附加边将其所连的两个点之间成为一个环主边，附加边各砍一刀问有多少种方案使得该图成两部分

砍一个未被覆盖过的主边后一次操作无论砍哪个附加边都可以
砍一个被覆盖一次的主边则后一次只能砍覆盖它的这个附加边
砍一个被覆盖两次以上的主边无论再怎么砍都不能将其分为两部分

所以进行一遍边差分然后枚举判断

我会说我又一次在读入s和t的时候用的while(m—)吗？？

/*
 id:lxyyyy
 树上差分 poj3417 边差分 
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
#define lson o<<1
#define rson o<<1|1
const int N=100000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827;
int n,m,cnt[N],f[N][25],dep[N],ans=0;
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}
int head[N],tot=0;
struct edge{
     int v,nxt;}e[N<<1];
void add(int u,int v){
    e[++tot]=(edge){v,head[u]};head[u]=tot;
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(rg int i=1;i<=20;++i){
        if(dep[u]<(1<<i)) break;
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa) continue;
        dfs(e[i].v,u);
    }
}
int LCA(int a,int b){
    if(dep[a]>dep[b]) swap(a,b);
    for(rg int i=20;i>=0;--i){
        if(dep[f[b][i]]<dep[a]) continue;
        b=f[b][i];
    }
    if(b==a) return a;
    for(rg int i=20;i>=0;--i){
        if(f[a][i]==f[b][i]) continue;
        a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}
void dfs2(int u,int fa){
    for(int i=head[u];i;i=e[i].nxt){
        if(e[i].v==fa) continue;
        dfs2(e[i].v,u);
        cnt[u]+=cnt[e[i].v];
    }
}
int main(){
//    freopen("yam1.in","r",stdin);
    rd(n),rd(m);
    for(int i=1,u,v;i<n;++i) rd(u),rd(v),add(u,v),add(v,u);
    int s,t,lca;
    dfs(1,0);
    for(int i=1;i<=m;++i){
        rd(s),rd(t);
        lca=LCA(s,t);
        ++cnt[s],++cnt[t],cnt[lca]-=2;
    }
    dfs2(1,0);
    for(int i=1;i<=n;++i){
        if(!cnt[i]&&i!=1) ans+=m;
        if(cnt[i]==1) ++ans;
    }
    printf("%d",ans);
    return 0;
}