图论———树上差分

时间：2022-12-19 15:35:45

基于我们已经了解了差分，那么下面我们来看看它的更深一层：

树上差分；

关于这一块重不重要呢，当然是有点重要的；

在NOIP2012借教室 ，NOIP2015运输计划 ，NOIP2016天天爱跑步 中考察的主要都是这个知识点；

下面进入正题；

树上差分主要分为点的差分和边的差分，在了解前缀和，差分，LCA的前提下，下面我们开始了解树上差分；

首先明确一下树的两个特性：

1.任意两个节点之间有且只有一条路径；

2.根节点确定时，一个节点只有一个父亲节点；

接下来，真真切切地进入正题：：：

一.点的差分:

图论———树上差分

 

来看一下这张图（有点丑），如果我们求一棵n个结点的树从u点走到v点，求这条路径上的点被经过的次数，显然，我们是需要它们的LCA的。通过静坐观察法，可以发现，我们需要将w[u]++,w[v]++,同时让w[LCA]--,w[fa[LCA]]--;

模板码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M = 2e5 + 10;
int p[M][30],w[M],dep[M],cnt,head[M],n,ans;
struct node{
    int to,next;
}e[M];

void add(int u,int v){
    e[++cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
}

void dfs(int u,int fa,int deep){
    dep[u] = deep;
    p[u][0] = fa;
    for(int i = head[u];i;i=e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v,u,deep+1);
    }
}

void get_fa(){
    for(int j = 1;(1<<j)<=n;j++)
        for(int i = 1;i <= n;i ++)
            p[i][j] = p[p[i][j-1]][j-1];
}

int lca(int a,int b){
    if(dep[a] > dep[b]) swap(a,b);
    int h = dep[b] - dep[a];
    for(int i = 0;(1<<i)<=h;i++){
        if((1<<i)&h) b = p[b][i];
    }
    if(a != b){
        for(int i = 20;i >= 0;i --){
            if(p[a][i] != p[b][i]){
                a = p[a][i]; b = p[b][i];
            }
        }
        a=p[a][0];
    }
    return a;
}

void dfs1(int u,int fa){
    for(int i = head[u];i;i = e[i].next){
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v,u);
        w[u] += w[v];
    }
    ans = max(ans,w[u]);
}

int main()
{
    int m,u,v;
    scanf("%d%d",&n,&m);

    for(int i = 1;i < n;i ++){
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs(1,0,1); get_fa();
    for(int i = 1;i <= m;i ++){
        scanf("%d%d",&u,&v);
        int k = lca(u,v);
        w[u]++; w[v]++; w[k]--;
        w[p[k][0]]--;
    }
    dfs1(1,0);
    printf("%d\n",ans);
}

二.边的差分：

图论———树上差分

来看一下这张图，思考一下，如何记录边值的变化，边的差分需要把边塞给点，变成下面这张图：

图论———树上差分

但是，这里的标记与点的差分并不一样，在这里，我们把边拆成两条链，由于在进行边的差分时并没有算u和v的LCA，那么便考虑把边从LCA一分为二；

u-->LCA，就要把w[u]++,w[LCA]--; 然后是LCA-->v,把w[v]++,w[LCA]--;合起来，就是w[u]++,w[v]++,w[LCA]-=2.

简单来说，

点权求和：若[x,y]两点之间路径上的所有点的权值+d，则w[x]+=d , w[y]+=d , w[LCA(x,y)]-=d , w[Fa[LCA(x,y)]]-=d；

边权求和：若[x,y]两点之间路径上的所有边的权值+d，则w[x]+=d , w[y]+=d , w[LCA(x,y)]-=d*2；

最后！！从根节点出发，求每个点在树上的前缀和（DFS）,时间复杂度为O(n).

当然，树上差分在于其思想，更多时候考察的是与其他知识点的结合，大多与LCA成双出现，主要都是针对树上路径问题.

下面可以来看一道题Alyona and a tree.

题意大致是：：一棵根节点为1的树，每个点都有点值a[i]，每条边也有权值， dist(v, u)表示从v到u边权和。现在给出“控制”的定义：对一个点u， 设点v在其子树上，且dis(u, v) ≤ av，则称u控制v。要求求出每个点控 制了多少个点。 1 ≤ n ≤ 2 × 10^5 , 1 ≤ ai ≤ 10^9.

我们来思考一下，

如果v可以控制u，那么从v到u的路上的所有结点都可以控制u，因为从v到u路上的dist(v, u)是递减的.那么可以每次遍历一个点的时候，二分找出根节点到当前点i路径上点， 找出dist(j, i)刚好大于a[i]的点，树上差分统计这条路径。 而后遍历当前点i的所有儿子结点k，w[i]+ = w[k]. 然后这题就可以解决了。

代码如下：

#include <bits/stdc++.h>
const int maxn=200007;
int cnt,head[maxn],a[maxn],fa[maxn][21],ans[maxn];
int n;
long long dis[maxn];
struct node{
    int to,w,nxt;
}e[maxn<<1];

void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

void dfs(int u){
    for(int i=1;i<=20;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    int now=u;
    for(int i=20;i>=0;i--)
        if(fa[now][i]&&dis[u]-dis[fa[now][i]]<=a[u])
            now=fa[now][i];
    ans[fa[now][0]]--;
    ans[fa[u][0]]++;
    for (int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        fa[v][0]=u;
        dis[v]=dis[u]+e[i].w;
        dfs(v);
        ans[u]+=ans[v];
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int p,w;
    for(int i=2;i<=n;i++){
        scanf("%d%d",&p,&w);
        add(p,i,w);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

 

 

下面再来看一道题Network.

题意大致是：：一棵有N个点的树，再往里面加入M条新边，现在要破坏其中的两 条边，要求一条是原来树中的边，一条是新边，使其不连通。求方案的 数量。 1 ≤ N ≤ 100000), 1 ≤ M ≤ 100000).

那么我们继续来思考一下，

对于新加的一条边来说，肯定会与之前的树形成一个环，而此时环 内的树上边和新加的这条边一同删除就会是一种方案。

而这道题是将所有新边都加入后的情况，那么我们看每条边，如果 没有与它形成环的情况，那么这条边删除肯定会使得图不连通，即情况 就会加M，也就是和新加的M条边任意组合都可以。

因而我们每次读入一条附加边，就给x到y的路径上的所有主要边记 录上“被覆盖一次”，对于我们想要切割的一条主要边，有以下3种情况：

1.若这条边被覆盖0次，则可以任意再切断一条附加边。

2.若这条边被覆盖1次，那么只能再切断唯一的一条附加边。

3.若这条边被覆盖2次及以上，没有可行的方案。

解析的过程有点长，我们要把每种可能的情况都考虑一下，其实代码写出来并不长，来看一下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+7;
int n,m,f[maxn][21],cf[maxn],dep[maxn];
struct node{
    int to,nxt;
}ed[maxn<<1];

int cnt=0,head[maxn];
void add(int x,int y){
    ed[++cnt].to=y;
    ed[cnt].nxt=head[x];
    head[x]=cnt;
}

void dfs(int x,int fa,int deep){
    dep[x]=deep;
    f[x][0]=fa;
    for(int i=head[x];i;i=ed[i].nxt){
        int v=ed[i].to;
        if(v==fa) continue;
        dfs(v,x,deep+1);
    }
}

void dfs(int u){
    for(int i=head[u];i;i=ed[i].nxt){
        int v=ed[i].to;
        if(v==f[u][0]) continue;
        dfs(v);
        cf[u]+=cf[v];
    }
}

int lca(int x,int y){
    if(dep[x]>dep[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[y][i]]>=dep[x])
            y=f[y][i];
    }
    if(x==y) return x;
    for(int i=20;i>=0;i--){
        if(f[y][i]!=f[x][i])
        y=f[y][i],x=f[x][i];
    }
    return f[x][0];
}

int main(){
    scanf("%d%d",&n,&m);
    int s,t;
    for(int i=1;i<n;i++){
        scanf("%d%d",&s,&t);
        add(s,t);
        add(t,s);
    }
    dfs(1,0,1);
    for(int i=1;(1<<i)<=n;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&s,&t);
        int k=lca(s,t);
        cf[s]++,cf[t]++,cf[k]-=2; 
    }
    dfs(1);
    int ans=0;
    for(int i=2;i<=n;i++){
        if(cf[i]==1) ans++;
        if(cf[i]==0) ans+=m;
    }
    printf("%d",ans);
    return 0;
}

 

OKK,到此，内容就差不多讲完了，巩固也差不多完了，想练练手的同学可以做做之前NOIP题，然后还有几题可以了解一下，Max Flow，Delivery Service.

标签：

相关文章