树上差分的两种形式(相遇 or 行程的交集 题解)

algorithm
solution
Published

October 24, 2020

Modified

October 24, 2020

emm,这很NOIP…

写这个的原因是今天考试一个sb差分树题居然杠了个树剖上去,杀鸡用了牛刀。

而且不止一次了…总是想不到子树和这种差分,淦

Anyway,简单写写吧。

树上差分的两种形式

  • 单点修改&链查询用差分转化为单点修改&树上前缀和

    class MPQU{public: //单点修改 & 树上前缀和 (Modify Point Query Up)
      BIT bit;
      MPQU(bool typ=0){if(typ==1) bit=BIT(dN);}
      void Add(ll u,ll w){bit.Add(st[u],w); bit.Add(ed[u],-w);}
      ll Query(ll u){return bit.Query(st[u]);}
    };
    class MPQL{public: //单点修改 & 链查询 (Modify Point Query Link)
      MPQU mpqu;
      MPQL(bool typ=0){if(typ==1) mpqu=MPQU(1);}
      void Add(ll u,ll w){mpqu.Add(u,w);}
      ll Query(ll u,ll v){ll lca=LCA(u,v); return mpqu.Query(u)+mpqu.Query(v)-mpqu.Query(lca)-mpqu.Query(fa[lca]);}
    }mpql;
  • 链修改&单点查询用差分转化为单点修改&子树和

    class MPQD{public: //单点修改 & 子树和 (Modify Point Query Down)
      BIT bit;
      MPQD(bool typ=0){if(typ==1) bit=BIT(dN);} 
      void Add(ll u,ll w){bit.Add(st[u],w);}
      ll Query(ll u){return bit.Query(ed[u])-bit.Query(st[u]-1);}
    };
    class MLQP{public: //链修改 & 单点查询 (Modify Link Query Point)
      MPQD mpqd;
      MLQP(bool typ=0){if(typ==1) mpqd=MPQD(1);}
      void Add(ll u,ll v){ll lca=LCA(u,v); mpqd.Add(u,1); mpqd.Add(v,1); mpqd.Add(lca,-1); mpqd.Add(fa[lca],-1);}
      ll Query(ll u){return mpqd.Query(u);}
    }mlqp;

三重封装

转化后的问题都能用DFS序+树状数组解决。(在上文代码中,树状数组用BIT封装,st, ed是DFS序)

本质:

  • 树上前缀和对应序列前缀和

  • 子树和对应序列后缀和

在序列上,前缀和、后缀和均能解决这两个问题。

而之所以在树上这两种形式求解的问题出现不同,是因为与序列相比,树是上小下大的。

相遇 or 行程的交集 题解

这道题综合的考察了两种差分,成功把我干翻(

[出处不明] 相遇 or 行程的交集

Description

  豪哥生活在一个n个点的树形城市里面,每一天都要走来走去。虽然走的是比较的多,但是豪哥在这个城市里面的朋友并不是很多。

  当某一天,猴哥给他展现了一下大佬风范之后,豪哥决定要获得一些交往机会来提升交往能力。豪哥现在已经物色上了一条友,打算和它(豪哥并不让吃瓜群众知道性别)交往。豪哥现在spy了一下这个人的所有行程起点和终点,豪哥打算从终点开始走到起点与其相遇。但是豪哥是想找话题的,他想知道以前有多少次行程和此次行程是有交集的,这样豪哥就可以搭上话了。这个路径与之前路径的有交集数量作为豪哥此次的交往机会。

  但是豪哥急着要做交往准备,所以算什么交往机会的小事情就交给你了。

Input

  第一行一个正整数n表示节点个数。

  接下来n-1行,每行两个正整数分别是u,v表示节点u和v之间有连边。

  接下来一行一个 正整数m表示路径个数。

  然后有m行,每行两个正整数分别是u,v分别表示u到v之间有一条路径。

Output

  输出共m行,每行一个整数,第i行表示豪哥在这条路径上获得的交往机会。

Sample Input

5
1 2
1 3
3 4
3 5
4
4 5
4 2
1 3
1 2

Sample Output

0
1
2
2

Hint

【数据范围与约定】

  对于20%的数据n,m≤2000

  对于另外20%的数据n,m≤50000

  对于另外10%的数据n,m≤200000,保证树形结构是一条链

  对于另外50%的数据n,m≤200000

简要题意:给你一棵树,然后按顺序输入若干条路径。问每次输入路径时该路径与前面已经输入的多少条路径有交集。

主要要想到把两条树上路径有交集转换为其中某条路径的LCA被另一条路径所覆盖

于是对于当前输入的路径,分当前路径覆盖了多少个之前路径的LCA当前路径的LCA被之前多少个路径覆盖讨论即可。前者是单点修改&链查询,后者是链修改&单点查询,按前文的方法做就可以了。

注意特判LCA重叠的情况,见代码。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef vector<ll> Vector;
typedef vector<ll>::iterator VecIt;
ll Rd(){
    ll ans=0;bool fh=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') fh=1; c=getchar();}
    while(c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
    if(fh) ans=-ans;
    return ans;
}

ll Lowbit(ll x){return x&(-x);}

const ll PTN=2E5+5; 
class BIT{public: 
    vector<ll> tr;ll n;
    BIT(){}
    BIT(ll n){this->n = n; tr=vector<ll>(n+1,0);}
    void Add(ll p,ll w){
        if(!p) return;
        for(ll i=p;i<=n;i+=Lowbit(i)) tr[i]+=w;
    }
    ll Query(ll p){
        ll ans=0;
        for(ll i=p;i>=1;i-=Lowbit(i)) ans+=tr[i];
        return ans;
    }
};

ll N;
Vector edge[PTN];
ll fa[PTN],dep[PTN],sz[PTN],son[PTN];
ll st[PTN],ed[PTN];ll dN;
void DFS1(ll u,ll father,ll depth){
    fa[u]=father;dep[u]=depth;sz[u]=1;son[u]=0;st[u]=++dN;
    for(VecIt it = edge[u].begin(); it!=edge[u].end(); it++){
        ll v=(*it);if(v==father) continue;
        DFS1(v,u,depth+1);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
    ed[u]=++dN;
}
ll tp[PTN];
void DFS2(ll u,ll toop){
    tp[u]=toop;
    if(son[u]) DFS2(son[u],toop);
    for(VecIt it = edge[u].begin(); it!=edge[u].end(); it++){
        ll v=(*it);if(v==fa[u]) continue;
        if(v!=son[u]) DFS2(v,v);
    }
}
ll LCA(ll u,ll v){
    while(tp[u]!=tp[v]){
        if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
        u=fa[tp[u]];
    }
    if(dep[u]<dep[v]) return u;
    else return v;
}

class MPQU{public: //单点修改 & 树上前缀和 (Modify Point Query Up)
    BIT bit;
    MPQU(bool typ=0){if(typ==1) bit=BIT(dN);}
    void Add(ll u,ll w){bit.Add(st[u],w); bit.Add(ed[u],-w);}
    ll Query(ll u){return bit.Query(st[u]);}
};
class MPQD{public: //单点修改 & 子树和 (Modify Point Query Down)
    BIT bit;
    MPQD(bool typ=0){if(typ==1) bit=BIT(dN);} 
    void Add(ll u,ll w){bit.Add(st[u],w);}
    ll Query(ll u){return bit.Query(ed[u])-bit.Query(st[u]-1);}
};
class MPQL{public: //单点修改 & 链查询 (Modify Point Query Link)
    MPQU mpqu;
    MPQL(bool typ=0){if(typ==1) mpqu=MPQU(1);}
    void Add(ll u,ll w){mpqu.Add(u,w);}
    ll Query(ll u,ll v){ll lca=LCA(u,v); return mpqu.Query(u)+mpqu.Query(v)-mpqu.Query(lca)-mpqu.Query(fa[lca]);}
}mpql;
class MLQP{public: //链修改 & 单点查询 (Modify Link Query Point)
    MPQD mpqd;
    MLQP(bool typ=0){if(typ==1) mpqd=MPQD(1);}
    void Add(ll u,ll v){ll lca=LCA(u,v); mpqd.Add(u,1); mpqd.Add(v,1); mpqd.Add(lca,-1); mpqd.Add(lca,-1);/*mpqd.Add(fa[lca],-1);*/} //特殊处理重叠LCA 
    ll Query(ll u){return mpqd.Query(u);}
}mlqp;
int main(){
    //freopen("meet.in","r",stdin);
    //freopen("meet.out","w",stdout);
    N=Rd();
    for(ll i=1;i<N;i++){
        ll u=Rd(),v=Rd();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dN=0;sz[0]=0;DFS1(1,0,0);
    DFS2(1,1);
    st[0]=0;ed[0]=0;
    mpql=MPQL(1);mlqp=MLQP(1); 
    ll qN=Rd();
    for(ll q=1;q<=qN;q++){
        ll u=Rd(),v=Rd();
        ll lca=LCA(u,v);
        
        printf("%lld\n",mpql.Query(u,v)+mlqp.Query(lca));
        mpql.Add(lca,1);
        mlqp.Add(u,v);
    }
    return 0;
}