网站备案信息填写,注册公司没有地址怎么解决,商贸公司起名大全最新,北京网站开发不限年龄中途摆烂了几天加上考试比赛啥的#xff0c;导致目前写博客断了。。差了好几天的题目没学了qwq#xff0c;现在还是按照每天学的东西来写博客吧
今天主要学了树链剖分#xff0c;怎么说呢#xff0c;虽然随便拿出今天写的一道题目来看#xff0c;码量都是一两百行的…中途摆烂了几天加上考试比赛啥的导致目前写博客断了。。差了好几天的题目没学了qwq现在还是按照每天学的东西来写博客吧
今天主要学了树链剖分怎么说呢虽然随便拿出今天写的一道题目来看码量都是一两百行的但是其实也不算太恶。。细说
树链剖分有两种重链剖分、长链剖分。前者特征是把“最大的”儿子成为重儿子把树分为若干条重链后者特征是把“最长链”称为长儿子把树分为若干条长链。不过在应用中重链应用更多故树链剖分一般默认为重链剖分。
重链剖分是提高树上搜索效率的一个高级方法。它按照一定规则把树剖分成一条条线性的不相交的链因此就将整棵树的操作转换成对链的操作从而使操作的复杂度转为O(logn)转为从重链部。重链剖分的一个特性每条链的DFS序是有序的因此可以使用线段数处理从而高效的解决一些树上的修改和查询问题。
首先我们来试试水——求lca
现在有两种方法求lca它的各种算法都是通过快速的向上跳到祖先节点来实现的。
一、倍增法用二进制递增直接向祖先跳
二、数链剖分的跳法是将树剖成从根到叶子的一条条链路链路之间不相交每条链上的任意两个相邻节点都是父子关系每条链路内的节点可以看作一个集合以链头为集链路上的节点查询lca时都指向链头从而实现快速跳。
下面我们来介绍几组概念
1、size[x]以x为根子树的大小对于每个点x儿子中size最大的作为他的重儿子剩下的为轻儿子
2、deep[x]x的深度
3、father[x]x的父亲
4、top[x]指x所有在重链顶端
5、重链重边连接形成重边连接起来形成的链每个点恰好属于一条重链
6、轻边连接x和x轻儿子的边
预处理两遍DFS
第一遍算出deep[x],size[x],father[x],son[x]
第二遍算出top[x]重儿子和父节点的链头相同
lcaLowest Common Ancestor所谓LCA是当给定一个有根树T时对于任意两个结点u、v找到一个离根最远的结点x使得x同时是u和v的祖先x 便是u、v的最近公共祖先
现在来一道题目
P3379 【模板】最近公共祖先LCA
话不多说直接上代码
#includebits/stdc.h
using namespace std;
const int N1e65;
int n,m,s;
int x,y;
int depth[N];
int sizee[N];
int son[N];
int top[N];
int fath[N];
int head[N];
struct ee
{int to;int from;
}edge[N1];
int cnt;
void add(int u,int v)
{cnt;edge[cnt].tov;edge[cnt].fromhead[u];head[u]cnt;
}//链式前向星存图
void dfs1(int u,int fa)
{depth[u]depth[fa]1;//孩子树高父亲树高1 fath[u]fa;//认父 sizee[u]1;//初始化u节点为本身 for(int ihead[u];i;iedge[i].from){int vedge[i].to;if(v!fa){fath[v]u;dfs1(v,u);sizee[u]sizee[v];if(!son[u]||sizee[son[u]]sizee[v])son[u]v;}}
}
void dfs2(int u,int topx)
{top[u]topx;if(!son[u])return ;dfs2(son[u],topx);//重链优先 for(int ihead[u];i;iedge[i].from){int vedge[i].to;if(v!fath[u]v!son[u])dfs2(v,v);//轻链 }
}
int main()
{cinnms;for(int i1;in;i){int u,v;cinuv;add(u,v);add(v,u);}dfs1(s,0);dfs2(s,s);for(int i1;im;i){cinxy;while(top[x]!top[y]){//xy不在同一重链 if(depth[top[x]]depth[top[y]])swap(x,y);//x成为更浅点 xfath[top[x]];//跳跃 }if(depth[x]depth[y])coutxendl;elsecoutyendl;}return 0;
}
现在我们来写树链剖分
在数量剖分中常常有如下几个应用:
1、修改某路径上各点的权值
2、查询某路径上节点的权值之和
3、修改以某点为根的子树上各点的权值
4、查询以某点为根的树上所有节点的权值之和
那么对于这样的模型我们就自然而然会想到线段数由于每条重链内部的节点是有序的因此可以按DFS序将它们安排在一个线段树上将每个重链看作一个连续的区间来对重链的内部进行修改和查询。 我们需要进行判断
如果x和y在一条重链上那么我们直接将X到Y这一条重链上各点权值累加并且通过线段数进行修改
如果x和y很不幸不在同一条重点上而在不同的子树那么这时候我们需要通过x到lca(x,y)和y到lca(x,y)这两条链上的点的权值进行修改即可。
——但是我们在编程时我们通常会在查询lca的同时对所经过的节点直接进行修改——
查询x到y的路径上所有节点权值之和同样的通过线段数进行查询然后并进行相关操作即可。
对于以x为根节点的子树上各点权值的修改并查询由于每棵子树上的所有节点的DFS序是连续的也就是说每棵子树对应一个连续的区间那么修改和查询子树与线段数对区间的修改和查询的操作就完全一致了。
题目
P3384 【模板】重链剖分/树链剖分
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e55;
ll n,m,r,p;
ll com;
ll head[N];
ll x,y,z;
ll deep[N],siz[N],father[N],son[N];
ll top[N];
ll a[N];
ll newa[N];
ll id[N];
ll cou;
ll res;
struct ed
{ll to,from;
}edge[N1];
ll cnt;
struct tr
{ll lazy;ll num;
}tree[N2];
void add(ll u,ll v)
{cnt;edge[cnt].tov;edge[cnt].fromhead[u];head[u]cnt;
}
void dfs1(ll x,ll fa)
{deep[x]deep[fa]1;siz[x]1;father[x]fa;for(ll ihead[x];i;iedge[i].from){ll vedge[i].to;if(v!fa){dfs1(v,x);siz[x]siz[v];if(!son[x]||siz[v]siz[son[x]])son[x]v;}}
}
void dfs2(ll x,ll topx)
{cou;top[x]topx;id[x]cou;newa[cou]a[x]%p;if(!son[x])return ;dfs2(son[x],topx);for(ll ihead[x];i;iedge[i].from){ll vedge[i].to;if(v!father[x]v!son[x])dfs2(v,v);}
}
//树链剖分
void build(ll rt,ll l,ll r)
{tree[rt].lazy0;if(lr){tree[rt].numnewa[l]%p;return ;}ll mid(lr)1;build(rt1,l,mid);build(rt1|1,mid1,r);tree[rt].num(tree[rt1].num%ptree[rt1|1].num%p)%p;
}
void pushdown(ll rt,ll l,ll r)
{ll mid(lr)1;tree[rt1].lazy(tree[rt1].lazytree[rt].lazy)%p;tree[rt1|1].lazy(tree[rt1|1].lazytree[rt].lazy)%p;tree[rt1].num(tree[rt1].num%ptree[rt].lazy*(mid-l1))%p;tree[rt1|1].num(tree[rt1|1].num%ptree[rt].lazy*(r-mid))%p;tree[rt].lazy0;
}
void addplus(ll rt,ll l,ll r,ll L,ll R,ll k)
{if(LlrR){tree[rt].lazyk%p;tree[rt].num(k*(r-l1))%p;return ;}if(tree[rt].lazy)pushdown(rt,l,r);ll mid(lr)1;if(Lmid)addplus(rt1,l,mid,L,R,k);if(Rmid)addplus(rt1|1,mid1,r,L,R,k);tree[rt].num(tree[rt1].num%ptree[rt1|1].num%p)%p;
}
void query(ll rt,ll l,ll r,ll L,ll R)
{if(lLrR){restree[rt].num%p;return ;}if(tree[rt].lazy)pushdown(rt,l,r);ll mid(lr)1;if(Lmid)query(rt1,l,mid,L,R);if(Rmid)query(rt1|1,mid1,r,L,R);
}
//区间操作
void addrange(ll x,ll y,ll k)
{k%p;while(top[x]!top[y]){if(deep[top[x]]deep[top[y]])swap(x,y);addplus(1,1,n,id[top[x]],id[x],k);xfather[top[x]];}if(deep[x]deep[y])swap(x,y);addplus(1,1,n,id[x],id[y],k);
}
void queryrange(ll x,ll y)
{ll ans0;while(top[x]!top[y]){if(deep[top[x]]deep[top[y]])swap(x,y);res0;query(1,1,n,id[top[x]],id[x]);ansres%p;xfather[top[x]];}if(deep[x]deep[y])swap(x,y);res0;query(1,1,n,id[x],id[y]);ansres%p;coutans%pendl;
}
//子树操作
void addsontree(ll x,ll k)
{addplus(1,1,n,id[x],id[x]siz[x]-1,k);return ;
}
void querysontree(ll x)
{res0;query(1,1,n,id[x],id[x]siz[x]-1);coutres%pendl;
}
int main()
{cinnmrp;for(ll i1;in;i)cina[i];for(ll i1;in;i){ll u,v;cinuv;add(u,v);add(v,u);}dfs1(r,0);dfs2(r,r);build(1,1,n);for(ll i1;im;i){cincom;if(com1){cinxyz;addrange(x,y,z);}if(com2){cinxy;queryrange(x,y);}if(com3){cinxz;addsontree(x,z);}if(com4){cinx;querysontree(x);}}return 0;
}
P3258 [JLOI2014] 松鼠的新家
比上面模版居然简单多了。。。线段树其实用不着建。。。害我debug好久
代码
#includebits/stdc.h
using namespace std;
const int N3e55;
int n;
int head[N];
int a[N],newa[N];
int id[N];
int father[N],deep[N],siz[N],son[N];
int top[N];
struct ee
{int to;int from;
}edge[N1];
int cnt;
int cou;
int res;
void add(int u,int v)
{cnt;edge[cnt].tov;edge[cnt].fromhead[u];head[u]cnt;
}
struct tr
{int lazy;int num;
}tree[N2];
void dfs1(int x,int fa)
{deep[x]deep[fa]1;father[x]fa;siz[x]1;for(int ihead[x];i;iedge[i].from){int vedge[i].to;if(vfa)continue;dfs1(v,x);siz[x]siz[v];if(!son[x]||siz[son[x]]siz[v])son[x]v;}
}
void dfs2(int x,int topx)
{top[x]topx;cou;id[x]cou;if(!son[x])return ;dfs2(son[x],topx);for(int ihead[x];i;iedge[i].from){int vedge[i].to;if(v!son[x]v!father[x])dfs2(v,v);}
}
void pushdown(int rt,int l,int r)
{int mid(rl)1;tree[rt1].lazytree[rt].lazy;tree[rt1|1].lazytree[rt].lazy;tree[rt1].numtree[rt].lazy*(mid-l1);tree[rt1|1].numtree[rt].lazy*(r-mid);tree[rt].lazy0;
}
void addplus(int rt,int l,int r,int L,int R,int k)
{if(lLrR){tree[rt].numk*(r-l1);tree[rt].lazyk;return ;}if(tree[rt].lazy)pushdown(rt,l,r);int mid(lr)1;if(Lmid)addplus(rt1,l,mid,L,R,k);if(Rmid)addplus(rt1|1,mid1,r,L,R,k);tree[rt].numtree[rt1].numtree[rt1|1].num;
}
void query(int rt,int l,int r,int L,int R)
{if(lLrR){restree[rt].num;return ;}if(tree[rt].lazy)pushdown(rt,l,r);int mid(lr)1;res0;if(Lmid)query(rt1,l,mid,L,R);if(Rmid)query(rt1|1,mid1,r,L,R);
}
void addrange(int x,int y,int k)
{while(top[x]!top[y]){if(deep[top[x]]deep[top[y]])swap(x,y);addplus(1,1,n,id[top[x]],id[x],k);xfather[top[x]];}if(deep[x]deep[y])swap(x,y);addplus(1,1,n,id[x],id[y],k);
}
void queryrange(int x)
{res0;query(1,1,n,id[x],id[x]);coutresendl;
}
int main()
{cinn;for(int i1;in;i)cina[i];for(int i1;in;i) {int u,v;cinuv;add(u,v);add(v,u);}dfs1(1,0);dfs2(1,1);for(int i1;in-1;i){addrange(a[i],a[i1],1);addrange(a[i1],a[i1],-1);}for(int i1;in;i)queryrange(i);return 0;
}
