网站使用的数据库主要有哪些,百度竞价推广代运营话术,徐州个人建站模板,房地产公司网站建设模板树链剖分的核心思想就是将一棵树剖分成一条一条的链
因为树不好处理 但链比较好处理
为了学会它 我们先要学会树上dfs#xff08;深度优先搜索#xff09; 然后就没了#xff08;雾#xff09;
Because 树链剖分需要用到两个dfs
哦对了 我们还要了解以下的知识点
1.子…树链剖分的核心思想就是将一棵树剖分成一条一条的链
因为树不好处理 但链比较好处理
为了学会它 我们先要学会树上dfs深度优先搜索 然后就没了雾
Because 树链剖分需要用到两个dfs
哦对了 我们还要了解以下的知识点
1.子树大小
就是一个节点的子树的节点个数包括它自己
2.重儿子
一个节点的所有儿子中子树大小最大的儿子
3.轻儿子
除了重儿子之外的儿子(包括根节点)
4.重边
两个相邻的重儿子连成的边
5.重链
重边连成的链开头是轻儿子
OK了解完了
启动
dfs1:
目标是求出以下数据
1 节点的父节点
2 节点的深度 也就是它到根节点的距离
3 节点的重儿子
4 节点的子树大小
思路十分的简单 直接上代码
void dfs1(int x)
{deep[x]deep[fa[x]]1;si[x]1;//它自己也是 for(int i0;ia[x].size();i){if(a[x][i]fa[x]) continue;fa[a[x][i]]x;dfs1(a[x][i]);si[x]si[a[x][i]];if(si[a[x][i]]si[son[x]]) son[x]a[x][i];}
}
dfs2:
目标是求出以下数据
1 节点的所在的重链的顶端节点
2 节点的新编号
3 节点的新编号的值
其中 新编号的原则是先走重儿子 再走轻儿子理由下次一定
比如 懂了吗 我相信你肯定懂了
思路也十分的简单 直接上代码
void dfs2(int x,int topf)
{id[x]cnt;top[x]topf;b[cnt]w[x];if(!son[x]) return;dfs2(son[x],topf);for(int i0;ia[x].size();i){if(a[x][i]fa[x]||a[x][i]son[x]){continue;}dfs2(a[x][i],a[x][i]);}
}
我们发现先走重儿子的话 就可以让重链上的点的新编号是连续的 也就形成了一条链
至此 树链剖分就结束了
那你一定很想问 这玩意有什么用呢
题目
我们结合题目来看其实是模板
前置芝士线段树
让我们处理4种操作
我们先来看操作3和操作4
通过观察图片可以看出 一个节点的子树的编号肯定是连续的
设子树的根是
左端点是的编号是 右端点的编号是
所以3操作就是将到加上
4操作就是求出到的值的和
即区间修改 区间查询
我们当然会想到线段树啦
直接拿下
之后我们来看1,2操作
先来看一看图 比如我们要从 7 到 4
我们可以先判断它俩的top是不是一个东西 发现不是
发现4的深度比7小 这怎么可以呢
我们交换一下 变成从 4 到 7
然后把4跳到它的top的父节点
也就是01的父节点是0
并加上 1 到 4 的值 可以用线段树处理
之后在循环上述操作
直到两者的top相等
上代码
int getsum1(int x,int y)
{int sum0;while(top[x]!top[y]){if(deep[top[x]]deep[top[y]]){swap(x,y);}sumsumquery(1,1,n,id[top[x]],id[x]);xfa[top[x]];}if(deep[x]deep[y]){swap(x,y);}sumquery(1,1,n,id[x],id[y]);return sum;
}
修改也差不多 直接上代码
void addsum1(int x,int y,int z)
{while(top[x]!top[y]){if(deep[top[x]]deep[top[y]]){swap(x,y);}add(1,1,n,id[top[x]],id[x],z);xfa[top[x]];}if(deep[x]deep[y]){swap(x,y);}add(1,1,n,id[x],id[y],z);
}
完整版
#includebits/stdc.h
#define int long long
using namespace std;
int n,cnt,m,r,mod;
int b[110000],top[110000],w[110000],deep[110000],id[110000],fa[110000],si[110000],son[110000],tr[410000],tag[410000];
vectorinta[110000];
void dfs1(int x)
{deep[x]deep[fa[x]]1;si[x]1;//它自己也是 for(int i0;ia[x].size();i){if(a[x][i]fa[x]) continue;fa[a[x][i]]x;dfs1(a[x][i]);si[x]si[a[x][i]];if(si[a[x][i]]si[son[x]]) son[x]a[x][i];}
}
void dfs2(int x,int topf)
{id[x]cnt;top[x]topf;b[cnt]w[x];if(!son[x]) return;dfs2(son[x],topf);for(int i0;ia[x].size();i){if(a[x][i]fa[x]||a[x][i]son[x]){continue;}dfs2(a[x][i],a[x][i]);}
}
void build(int k,int l,int r)
{if(lr){tr[k]b[l];return;}int mid(lr)1;build(k1,l,mid);build(k1|1,mid1,r);tr[k]tr[k1]tr[k1|1];
}
void push_down(int k,int l,int r)
{if(tag[k]){int mid(lr)1;tag[k1]tag[k];tag[k1|1]tag[k];tr[k1](mid-l1)*tag[k];tr[k1|1](r-mid)*tag[k];tag[k]0;}
}
void add(int k,int l,int r,int q,int p,int d)
{if(qlpr){tag[k]d;tr[k](r-l1)*d;return;}push_down(k,l,r);int mid(lr)1;if(midq){add(k1,l,mid,q,p,d);}if(midp){add(k1|1,mid1,r,q,p,d);}tr[k](tr[k1]tr[k1|1]);
}
int query(int k,int l,int r,int q,int p)
{if(qlpr){return tr[k];}push_down(k,l,r);int mid(lr)1,ssum0;if(midq){ssumquery(k1,l,mid,q,p);}if(midp){ssumquery(k1|1,mid1,r,q,p);}return ssum;
}
int getsum1(int x,int y)
{int sum0;while(top[x]!top[y]){if(deep[top[x]]deep[top[y]]){swap(x,y);}sumsumquery(1,1,n,id[top[x]],id[x]);xfa[top[x]];}if(deep[x]deep[y]){swap(x,y);}sumquery(1,1,n,id[x],id[y]);return sum;
}
int getsum2(int x)
{return query(1,1,n,id[x],id[x]si[x]-1);
}
void addsum1(int x,int y,int z)
{while(top[x]!top[y]){if(deep[top[x]]deep[top[y]]){swap(x,y);}add(1,1,n,id[top[x]],id[x],z);xfa[top[x]];}if(deep[x]deep[y]){swap(x,y);}add(1,1,n,id[x],id[y],z);
}
void addsum2(int x,int y)
{add(1,1,n,id[x],id[x]si[x]-1,y);
}
signed main()
{scanf(%lld%lld%lld%lld,n,m,r,mod);for(int i1;in;i){scanf(%lld,w[i]);}for(int i1;in;i){int x,y;scanf(%lld%lld,x,y);a[x].push_back(y);a[y].push_back(x);}dfs1(r);dfs2(r,r);build(1,1,n);while(m--){int op;scanf(%lld,op);if(op1){int x,y,z;scanf(%lld%lld%lld,x,y,z);addsum1(x,y,z);}if(op2){int x,y;scanf(%lld%lld,x,y);printf(%lld\n,getsum1(x,y)%mod);}if(op3){int x,y;scanf(%lld%lld,x,y);addsum2(x,y);}if(op4){int x;scanf(%lld,x);printf(%lld\n,getsum2(x)%mod);}}return 0;
}
