树上差分的两种形式(相遇 or 行程的交集 题解)
emm,这很NOIP…
写这个的原因是今天考试一个sb差分树题居然杠了个树剖上去,杀鸡用了牛刀。
而且不止一次了…总是想不到子树和这种差分,淦
Anyway,简单写写吧。
树上差分的两种形式
单点修改&链查询用差分转化为单点修改&树上前缀和
class MPQU{public: //单点修改 & 树上前缀和 (Modify Point Query Up) ; BIT bit(bool typ=0){if(typ==1) bit=BIT(dN);} MPQUvoid Add(ll u,ll w){bit.Add(st[u],w); bit.Add(ed[u],-w);} (ll u){return bit.Query(st[u]);} ll Query}; class MPQL{public: //单点修改 & 链查询 (Modify Point Query Link) ; MPQU mpqu(bool typ=0){if(typ==1) mpqu=MPQU(1);} MPQLvoid Add(ll u,ll w){mpqu.Add(u,w);} (ll u,ll v){ll lca=LCA(u,v); return mpqu.Query(u)+mpqu.Query(v)-mpqu.Query(lca)-mpqu.Query(fa[lca]);} ll Query}mpql;
链修改&单点查询用差分转化为单点修改&子树和
class MPQD{public: //单点修改 & 子树和 (Modify Point Query Down) ; BIT bit(bool typ=0){if(typ==1) bit=BIT(dN);} MPQDvoid Add(ll u,ll w){bit.Add(st[u],w);} (ll u){return bit.Query(ed[u])-bit.Query(st[u]-1);} ll Query}; class MLQP{public: //链修改 & 单点查询 (Modify Link Query Point) ; MPQD mpqd(bool typ=0){if(typ==1) mpqd=MPQD(1);} MLQPvoid 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 u){return mpqd.Query(u);} ll Query}mlqp;
三重封装
转化后的问题都能用DFS序+树状数组解决。(在上文代码中,树状数组用BIT
封装,st, ed
是DFS序)
本质:
树上前缀和对应序列前缀和
子树和对应序列后缀和
在序列上,前缀和、后缀和均能解决这两个问题。
而之所以在树上这两种形式求解的问题出现不同,是因为与序列相比,树是上小下大的。
相遇 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=0;bool fh=0;char c=getchar();
ll answhile(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 x){return x&(-x);}
ll Lowbit
const ll PTN=2E5+5;
class BIT{public:
<ll> tr;ll n;
vector(){}
BIT(ll n){this->n = n; tr=vector<ll>(n+1,0);}
BITvoid Add(ll p,ll w){
if(!p) return;
for(ll i=p;i<=n;i+=Lowbit(i)) tr[i]+=w;
}
(ll p){
ll Query=0;
ll ansfor(ll i=p;i>=1;i-=Lowbit(i)) ans+=tr[i];
return ans;
}
};
;
ll N[PTN];
Vector edge[PTN],dep[PTN],sz[PTN],son[PTN];
ll fa[PTN],ed[PTN];ll dN;
ll stvoid DFS1(ll u,ll father,ll depth){
[u]=father;dep[u]=depth;sz[u]=1;son[u]=0;st[u]=++dN;
fafor(VecIt it = edge[u].begin(); it!=edge[u].end(); it++){
=(*it);if(v==father) continue;
ll v(v,u,depth+1);
DFS1[u]+=sz[v];
szif(sz[v]>sz[son[u]]) son[u]=v;
}
[u]=++dN;
ed}
[PTN];
ll tpvoid DFS2(ll u,ll toop){
[u]=toop;
tpif(son[u]) DFS2(son[u],toop);
for(VecIt it = edge[u].begin(); it!=edge[u].end(); it++){
=(*it);if(v==fa[u]) continue;
ll vif(v!=son[u]) DFS2(v,v);
}
}
(ll u,ll v){
ll LCAwhile(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
=fa[tp[u]];
u}
if(dep[u]<dep[v]) return u;
else return v;
}
class MPQU{public: //单点修改 & 树上前缀和 (Modify Point Query Up)
;
BIT bit(bool typ=0){if(typ==1) bit=BIT(dN);}
MPQUvoid Add(ll u,ll w){bit.Add(st[u],w); bit.Add(ed[u],-w);}
(ll u){return bit.Query(st[u]);}
ll Query};
class MPQD{public: //单点修改 & 子树和 (Modify Point Query Down)
;
BIT bit(bool typ=0){if(typ==1) bit=BIT(dN);}
MPQDvoid Add(ll u,ll w){bit.Add(st[u],w);}
(ll u){return bit.Query(ed[u])-bit.Query(st[u]-1);}
ll Query};
class MPQL{public: //单点修改 & 链查询 (Modify Point Query Link)
;
MPQU mpqu(bool typ=0){if(typ==1) mpqu=MPQU(1);}
MPQLvoid Add(ll u,ll w){mpqu.Add(u,w);}
(ll u,ll v){ll lca=LCA(u,v); return mpqu.Query(u)+mpqu.Query(v)-mpqu.Query(lca)-mpqu.Query(fa[lca]);}
ll Query}mpql;
class MLQP{public: //链修改 & 单点查询 (Modify Link Query Point)
;
MPQD mpqd(bool typ=0){if(typ==1) mpqd=MPQD(1);}
MLQPvoid 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 u){return mpqd.Query(u);}
ll Query}mlqp;
int main(){
//freopen("meet.in","r",stdin);
//freopen("meet.out","w",stdout);
=Rd();
Nfor(ll i=1;i<N;i++){
=Rd(),v=Rd();
ll u[u].push_back(v);
edge[v].push_back(u);
edge}
=0;sz[0]=0;DFS1(1,0,0);
dN(1,1);
DFS2[0]=0;ed[0]=0;
st=MPQL(1);mlqp=MLQP(1);
mpql=Rd();
ll qNfor(ll q=1;q<=qN;q++){
=Rd(),v=Rd();
ll u=LCA(u,v);
ll lca
("%lld\n",mpql.Query(u,v)+mlqp.Query(lca));
printf.Add(lca,1);
mpql.Add(u,v);
mlqp}
return 0;
}