樹(shù)上差分利用前綴和的思想，利用樹(shù)上的前綴和（也就是子樹(shù)和），記錄樹(shù)上的一些信息，因?yàn)樗梢赃M(jìn)行離線操作，復(fù)雜度O（n），時(shí)間、空間、代碼復(fù)雜度都十分優(yōu)秀。

最大流
FJ給他的牛棚的N(2≤N≤50,000)個(gè)隔間之間安裝了N-1根管道，隔間編號(hào)從1到N。所有隔間都被管道連通了。
FJ有K(1≤K≤100,000)條運(yùn)輸牛奶的路線，第i條路線從隔間si運(yùn)輸?shù)礁糸gti。一條運(yùn)輸路線會(huì)給它的兩個(gè)端點(diǎn)處的隔間以及中間途徑的所有隔間帶來(lái)一個(gè)單位的運(yùn)輸壓力，你需要計(jì)算壓力最大的隔間的壓力是多少。

這道題需要讓我們求出每個(gè)點(diǎn)的覆蓋次數(shù)（這顯然可以用樹(shù)鏈剖分來(lái)做），但這也是一個(gè)樹(shù)上差分的經(jīng)典題。

拋開(kāi)這道題，先考慮對(duì)于一維的一個(gè)空間，我們?nèi)绾尾罘?#xff0c;沒(méi)錯(cuò)，對(duì)于區(qū)間（l-r）來(lái)說(shuō)，在l出加上1，在r+1處減去1，再求前綴和即可。

那在樹(shù)上如何操作，我們可以把樹(shù)抽象的想象成自下而上的一個(gè)數(shù)組，對(duì)于一段連續(xù)的鏈，在下面的端點(diǎn)加上1，在上面的端點(diǎn)的父節(jié)點(diǎn)減去1，求子樹(shù)和。

那么左右端點(diǎn)不在一條直鏈上怎么辦？可以考慮使用lCA，對(duì)于兩個(gè)點(diǎn)的LCA來(lái)說(shuō)，LCA才這條鏈上只出現(xiàn)了一次，所以在兩個(gè)端點(diǎn)分別加1，LCA-1，LCA的父親減1，求子樹(shù)和，這道題就水過(guò)了。

?

#include<iostream> #include<cstdio> #define N 50009 using namespace std; int ans,head[N],ji[N],tot,deep[N],p[N][22],n,m,a,b,c,fa[N]; struct de {int n,to; }an[N<<1]; inline void add(int u,int v) {an[++tot].n=head[u];an[tot].to=v;head[u]=tot; } void dfs(int u,int f) {deep[u]=deep[f]+1;fa[u]=f;p[u][0]=f;for(int i=1;(1<<i)<=deep[u];++i)p[u][i]=p[p[u][i-1]][i-1];for(int i=head[u];i;i=an[i].n)if(an[i].to!=f){int v=an[i].to;dfs(v,u);} } inline int getlca(int a,int b) {if(deep[a]<deep[b])swap(a,b);for(int i=20;i>=0;--i)if(deep[a]-(1<<i)>=deep[b])a=p[a][i];if(a==b)return b;for(int i=20;i>=0;--i)if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i];return p[a][0]; } void dfs2(int u) {for(int i=head[u];i;i=an[i].n)if(an[i].to!=fa[u]){int v=an[i].to;dfs2(v);ji[u]+=ji[v];}ans=max(ans,ji[u]); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<n;++i)scanf("%d%d",&a,&b),add(a,b),add(b,a);dfs(1,0);for(int i=1;i<=m;++i){scanf("%d%d",&a,&b);c=getlca(a,b);ji[c]--;ji[fa[c]]--;ji[a]++;ji[b]++;}dfs2(1);cout<<ans;return 0; }

?

再來(lái)道難一點(diǎn)的。

NOIP2015運(yùn)輸計(jì)劃
公元 20442044 年，人類進(jìn)入了宇宙紀(jì)元。
L 國(guó)有 n 個(gè)星球，還有 n-1 條雙向航道，每條航道建立在兩個(gè)星球之間，這 n-1 條航道連通了 L國(guó)的所有星球。
小 P 掌管一家物流公司， 該公司有很多個(gè)運(yùn)輸計(jì)劃，每個(gè)運(yùn)輸計(jì)劃形如：有一艘物流飛船需要從 u 號(hào)星球沿最快的宇航路徑飛行到 v 號(hào)星球去。顯然，飛船駛過(guò)一條航道是需要時(shí)間的，對(duì)于航道 j ，任意飛船駛過(guò)它所花費(fèi)的時(shí)間為 t ，并且任意兩艘飛船之間不會(huì)產(chǎn)生任何干擾。
為了鼓勵(lì)科技創(chuàng)新， L國(guó)國(guó)王同意小 P的物流公司參與 L 國(guó)的航道建設(shè)，即允許小 P 把某一條航道改造成蟲(chóng)洞，飛船駛過(guò)蟲(chóng)洞不消耗時(shí)間。
在蟲(chóng)洞的建設(shè)完成前小 P 的物流公司就預(yù)接了 m 個(gè)運(yùn)輸計(jì)劃。在蟲(chóng)洞建設(shè)完成后，這 m 個(gè)運(yùn)輸計(jì)劃會(huì)同時(shí)開(kāi)始，所有飛船一起出發(fā)。當(dāng)這 m 個(gè)運(yùn)輸計(jì)劃都完成時(shí)，小 P 的物流公司的階段性工作就完成了。
如果小 P可以自由選擇將哪一條航道改造成蟲(chóng)洞， 試求出小 P 的物流公司完成階段性工作所需要的最短時(shí)間是多少？

問(wèn)題來(lái)了，剛才我們要求點(diǎn)的覆蓋次數(shù)，這回要求邊，我們都知道求點(diǎn)的覆蓋可以用樹(shù)鏈剖分來(lái)做，
但把點(diǎn)換成邊好像無(wú)從下手(不過(guò)好像也可以做。但復(fù)雜度不是太好看

那么我們?cè)撊绾翁幚?#xff1f;
還是樹(shù)上差分，但我們把定義換一下，把邊上的信息放到點(diǎn)上，每個(gè)子樹(shù)記錄的是這個(gè)點(diǎn)向上連的那條邊出現(xiàn)的次數(shù)，左右端點(diǎn)分別加1，LCA減2，就可以搞了。

然后咧？

我們發(fā)現(xiàn)直接求很困難，所以就考慮把求最值改成二分答案+驗(yàn)證找最值，先二分最終的答案，那么大于這個(gè)答案的鏈?zhǔn)切枰獎(jiǎng)h邊的，在把需要?jiǎng)h邊的鏈來(lái)一波差分，找出這些鏈的最長(zhǎng)公共鏈，判斷把這條鏈刪掉之后答案是否合法，然后這題就做完了。

　　

#include<iostream> #include<cstdio> #include<cstring> #define N 300009 #define R register using namespace std; int tot,head[N],ji[N],jii[N],num,ll,lca[N],u[N],v[N],n,deep[N],d[N],fa[N],m,L[N],p[N][22]; int a,b,c,l,r; struct de {int n,to,l; }an[N<<1]; inline void add(int u,int v,int l) {an[++tot].n=head[u];an[tot].to=v;head[u]=tot;an[tot].l=l; } void dfs2(int u,int fa) {for(R int i=head[u];i;i=an[i].n)if(an[i].to!=fa){int v=an[i].to;dfs2(v,u);ji[u]+=ji[v];}if(ji[u]==num)ll=max(ll,jii[u]); } bool ch(int pos) {int pp=0;num=0;ll=0;memset(ji,0,sizeof(ji));for(R int i=1;i<=m;++i)if(L[i]>pos){ji[lca[i]]-=2;ji[u[i]]++;ji[v[i]]++;pp=max(pp,L[i]);num++;}dfs2(1,0);if(pp-ll<=pos)return 1;else return 0; } void dfs(int u,int f) {fa[u]=f;deep[u]=deep[f]+1;p[u][0]=f;for(R int i=1;(1<<i)<=deep[u];++i)p[u][i]=p[p[u][i-1]][i-1];for(R int i=head[u];i;i=an[i].n)if(an[i].to!=f){int v=an[i].to;d[v]=d[u]+an[i].l;jii[v]=an[i].l;dfs(v,u);} } inline int getlca(int a,int b) {if(deep[a]<deep[b])swap(a,b);for(R int i=20;i>=0;--i)if(deep[a]-(1<<i)>=deep[b])a=p[a][i];if(a==b)return b;for(R int i=20;i>=0;--i)if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i];return p[a][0]; } int rd() {int x=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar(); }return x; } int main() {n=rd();m=rd();for(R int i=1;i<n;++i)a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);dfs(1,0);for(R int i=1;i<=m;++i){u[i]=rd();v[i]=rd(); lca[i]=getlca(u[i],v[i]);L[i]=d[u[i]]+d[v[i]]-2*d[lca[i]];r=max(r,L[i]);}int ans=0;while(l<=r){int mid=(l+r)>>1;if(ch(mid)){ans=mid;r=mid-1;}else l=mid+1;}cout<<ans;return 0; }

來(lái)看最后一道 NOIP2016 天天愛(ài)跑步

這是我見(jiàn)過(guò)的最難的一道樹(shù)上差分題目，它的解法十分的巧妙。

在第w[j]秒觀察到，難道我還讓它動(dòng)態(tài)的往上跳嗎？

當(dāng)然不用，讓我們列一波式子。

因?yàn)檫@是一顆樹(shù)，它具有一些非常有用（惡心）的性質(zhì)，就是鏈上的LCA，當(dāng)w在s到LCA的路上時(shí)，有以下式子成立

deep[S]=w[x]+deep[x]

當(dāng)w在LCA到t的路上時(shí)，有以下式子成立
deep[s]-2*d[lca(s,t)]=w[x]-deep[x]

由于二式不等價(jià)，所以我們要分開(kāi)處理，由于在S到LCA的路上一式成立，在LCA到T時(shí)二式成立，但我們?cè)谔幚韮煞N情況時(shí)要注意不能重復(fù)。

所以我們開(kāi)兩個(gè)映射，第一個(gè)表示在一式情況下左邊的式子的結(jié)果對(duì)應(yīng)了幾個(gè)x，第二個(gè)表示二式下左邊的式子的結(jié)果對(duì)應(yīng)了幾個(gè)x。

然后怎么做？

還考慮樹(shù)上差分，我們可以理解為又有一種數(shù)在s出現(xiàn)，在lca的父親處消失，另一種樹(shù)在t出現(xiàn)，在LCA處消失，這兩種數(shù)對(duì)應(yīng)了上述兩種式子，那我們遍歷整棵樹(shù)時(shí)，到達(dá)一個(gè)節(jié)點(diǎn)就把這個(gè)位置對(duì)應(yīng)的結(jié)果加入映射，對(duì)于每個(gè)詢問(wèn)的答案，就是遍歷以這個(gè)點(diǎn)為根的子樹(shù)前后右邊的式子的結(jié)果對(duì)應(yīng)的映射的差。

#include<iostream> #include<cstdio> #include<vector> #include<map> #define N 300009 using namespace std; map<int,int>A,B; struct pai {int tag,tag2,num; }; vector<pai>ji[N]; int n,m,head[N],p[N][22],deep[N],fa[N],tot,a,b,w[N],ans[N]; struct dwd {int n,to; }an[N<<1]; inline void add(int u,int v) {an[++tot].n=head[u];an[tot].to=v;head[u]=tot; } void dfs(int u,int f) {fa[u]=f;deep[u]=deep[f]+1;p[u][0]=f;for(int i=1;(1<<i)<=deep[u];++i)p[u][i]=p[p[u][i-1]][i-1];for(int i=head[u];i;i=an[i].n){int v=an[i].to;if(v!=f)dfs(v,u);} } inline int getlca(int a,int b) {if(deep[a]<deep[b])swap(a,b);for(int i=20;i>=0;--i)if(deep[a]-(1<<i)>=deep[b])a=p[a][i];if(a==b)return b;for(int i=20;i>=0;--i)if(p[a][i]!=p[b][i])a=p[a][i],b=p[b][i];return p[a][0]; } void dfs2(int u,int fa) { int p=A[deep[u]+w[u]],q=B[w[u]-deep[u]];//gaifor(int i=head[u];i;i=an[i].n)if(an[i].to!=fa){int v=an[i].to;dfs2(v,u);} for(int i=0;i<ji[u].size();++i){if(ji[u][i].tag==1)A[ji[u][i].num]+=ji[u][i].tag2;else B[ji[u][i].num]+=ji[u][i].tag2;}ans[u]=B[w[u]-deep[u]]+A[deep[u]+w[u]]-q-p; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<n;++i)scanf("%d%d",&a,&b),add(a,b),add(b,a);dfs(1,0);for(int i=1;i<=n;++i)scanf("%d",&w[i]);for(int i=1;i<=m;++i){int s,t,lca;scanf("%d%d",&s,&t);lca=getlca(s,t);ji[s].push_back(pai{1,1,deep[s]});ji[fa[lca]].push_back(pai{1,-1,deep[s]});ji[t].push_back(pai{2,1,deep[s]-2*deep[lca]});ji[lca].push_back(pai{2,-1,deep[s]-2*deep[lca]});}dfs2(1,0);for(int i=1;i<=n;++i)printf("%d ",ans[i]);return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZH-comld/p/9384690.html

總結(jié)

以上是生活随笔為你收集整理的树上差分学习笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。