中山网站百度优化,沧州建设网站的公司,芜湖又出现一例,网站设计科技有限公司我们前面也学过差分#xff0c;现在的话我们就把他放到树上来做。因为这是树#xff0c;所以会有点和边之分#xff0c;所以树上差分也会分为 点差分 和 边差分 。
引入
树上差分其实和线性差分没有什么区别#xff0c;只不过是放到了树上的两点#xff0c;而他们之间的…我们前面也学过差分现在的话我们就把他放到树上来做。因为这是树所以会有点和边之分所以树上差分也会分为 点差分 和 边差分 。
引入
树上差分其实和线性差分没有什么区别只不过是放到了树上的两点而他们之间的最简路径就是可以类比成线性的两点之间的线段。 所以我们如果要对一条曲线进行操作的话就是在树上跑差分那么树上差分数组究竟是什么呢他又代表着什么意思呢这是一个值得深思的问题也是困扰我很久的问题。
树上差分数组本质上存储的是 操纵方式而不是简单的差值。例如一个点 x x x 的差分数组 p [ x ] − 3 p[x]-3 p[x]−3 代表这个点或这个点所对应的边被减去了3而不是这个点或这个边等于-3这是一个易错也易混的点。
相同的对线性差分数组进行求前缀和的话我们就可以得到真实的答案的值那么类似的在 树上差分数组中求子树和就可以的到这个点的操纵方式不过为什么要求子树和而不求其它的我也不知道我也不敢问。
点差分
如果我们现在要对树上的一条路径上的点进行统一操作比如说 1 或 -2我们应该如何完成 首先是不是很容易想到暴力 dfs 但是这样的时间复杂度是 O ( n 2 ) \cal O(n^2) O(n2) 的不优秀。但是我们在学什么是不是在学差分那为什么不从差分的视角来考虑考虑
如果我们要对一条 A → B A \rightarrow B A→B 的路径进行1的修改操作那么首先我们肯定要在点 A A A 和 B B B 两个位置进行修改对吧又因为我们最后是通过求子树和来求得每个点的修改方式所以不能影响 点 A A A 和 点 B B B 所对应的子树所以我们可以非常明了的得到 p [ A ] , p [ B ] p[A],p[B] p[A],p[B] 然后我们的目光不断向上看发现基本上都没有问题但是在他们的最近公共祖先那里除了岔子为什么呢因为二者是从两端慢慢爬上来的这就会导致他们的 LCA 会被增加两次所以我们又可以得到 p [ l c a ( A , B ) ] − − p[lca(A,B)]-- p[lca(A,B)]−− 我们继续往上看发现点 A A A 和点 B B B 的最近公共祖先的父亲在计算子树和的时候任然会被增加一次但是他应该是不能被修改的所以我们还可以得到 p [ f a ( l c a ( A , B ) ) ] − − p[fa(lca(A,B))]-- p[fa(lca(A,B))]−− 继续往上看发现没有问题了说明我们的操作就成功的完成了看不懂的看下面的图示 我们把上述的公式总结一下就是 两个点自己加他们的lca和lca的爸爸都要减把它写成代码就是
//dp 为倍增数组lca为求最近公共祖先的函数
int rootlca(a,b);
p[a],p[b];
p[root]--,p[dp[root][0]]--;那么当我们要求所有的答案的时候也就是要求子树和的时候我们就可以使用一个时间复杂度为 O ( n ) \cal O(n) O(n) 的 dfs 函数来求解
//mp为邻接表存储
void get(int x, int fa) {int len mp[x].size();for (int i 0; i len; i) {if (mp[x][i] fa) continue;int t mp[x][i];get(t, x);p[x] p[t];//差分数组求子树和}
}看完后是不是感觉非常简单就只是在树上倍增的基础上对一个数组进行了一点点操作那么好我们上实战
例题1——wwx的出玩
wwx给她的衣柜的有 n 个隔间隔间编号为1到 n 。她有 k 天要和她的男朋友出去玩第 i 次玩耍wwx会穿隔间 si 到隔间 ti 的衣服每次穿这些衣服都会给它们带来一个单位的损坏你作为她的男朋友请计算损坏程度最大的衣服的损坏程度是多少。
分析与解答
不难发现这道题就是一道裸的点差分问题所以我们直接套模板顺便也把模板给你了。
#includebits/stdc.h
using namespace std;
const int INF1e5;
vectorint mp[INF];
int ans,dp[INF][20],deep[INF],num[INF];//num为差分数组void prepare(int x,int fa){for (int j1;(1j)deep[x]-1;j){dp[x][j]dp[dp[x][j-1]][j-1];} int lenmp[x].size();for (int i0;ilen;i){if (mp[x][i]fa)continue;int tmp[x][i];deep[t]deep[x]1,dp[t][0]x;prepare(t,x); }
}int lca(int x,int y){if (deep[x]deep[y])swap(x,y);int index__lg(deep[x]-deep[y]);for (int iindex;i0;i--){if (deep[dp[x][i]]deep[y])xdp[x][i];if (deep[x]deep[y])break;}if (xy)return x;for (int i18;i0;i--){if (dp[x][i]!dp[y][i])xdp[x][i],ydp[y][i];}return dp[x][0];
}void get(int x,int fa){int lenmp[x].size();for (int i0;ilen;i){if (mp[x][i]fa)continue;int tmp[x][i];get(t,x);num[x]num[t];}ansmax(ans,num[x]);//求得最大值
}
int main(){int n,k;cinnk;for (int i1;in;i){int u,v;cinuv;mp[u].push_back(v);mp[v].push_back(u);} deep[1]1;prepare(1,-1);for (int i1;ik;i){int s,t;cinst;int rootlca(s,t);num[s],num[t],num[root]--,num[dp[root][0]]--;}get(1,-1);coutans;return 0;
}例题2——松鼠的新家
题目传送门
分析与解答
这道题其实也是裸题我们稍微分析一下就知道它的那个参观路线是可以被分成多个区间修改的但是这样的话他们的端点的位置会被重复计算所以要特判
#includebits/stdc.h
using namespace std;
const int INF3e510;
vectorint mp[INF];
int ans,dp[INF][20],deep[INF];
int a[INF],num[INF];void prepare(int x,int fa){for (int j1;(1j)deep[x]-1;j){dp[x][j]dp[dp[x][j-1]][j-1];} int lenmp[x].size();for (int i0;ilen;i){if (mp[x][i]fa)continue;int tmp[x][i];deep[t]deep[x]1,dp[t][0]x;prepare(t,x); }
}int lca(int x,int y){if (deep[x]deep[y])swap(x,y);int index__lg(deep[x]-deep[y]);for (int iindex;i0;i--){if (deep[dp[x][i]]deep[y])xdp[x][i];if (deep[x]deep[y])break;}if (xy)return x;for (int i18;i0;i--){if (dp[x][i]!dp[y][i])xdp[x][i],ydp[y][i];}return dp[x][0];
}void get(int x,int fa){int lenmp[x].size();for (int i0;ilen;i){if (mp[x][i]fa)continue;int tmp[x][i];get(t,x);num[x]num[t];}ansmax(ans,num[x]);
}
int main(){int n;cinn;for (int i1;in;i){scanf(%d,a[i]);}for (int i1;in;i){int u,v;scanf(%d%d,u,v);mp[u].push_back(v);mp[v].push_back(u);} deep[1]1;prepare(1,-1);for (int i1;in;i){int sa[i],ta[i1];int rootlca(s,t);num[s],num[t],num[root]--,num[dp[root][0]]--;}get(1,-1);for (int i2;in;i){num[a[i]]--;}for (int i1;in;i){printf(%d\n,num[i]);}return 0;
}
