【2019.7.10】树上差分杂[LCA 倍增][树上差分点差分边差分]

迷南。 2021-11-17 15:44 302阅读 0赞

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

## **点差分** ##

### [**P3128** \[USACO15DEC\]最大流Max Flow][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\]松鼠的新家][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 3417][]****[loj暗的连锁][loj]**    ###

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

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

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

我会说我又一次在读入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;
    }

POJ3417

### [【luogu2680】【noip2015】 运输计划 \[LCA 树上差分 边差分\]\[二分\]][luogu2680_noip2015_ _ _LCA _] ###

[P3128_ _USACO15DEC_Max Flow]: https://www.luogu.org/problemnew/show/P3128
[P3258_ _JLOI2014]: https://www.luogu.org/problemnew/show/P3258
[POJ 3417]: http://poj.org/problem?id=3417
[loj]: https://loj.ac/problem/10131
[luogu2680_noip2015_ _ _LCA _]: https://www.cnblogs.com/lxyyyy/p/11166317.html