未完待续
考完大联盟了~~~~~~
放四天假了~~~~~~
回来学（fu）习（bai）啦~~~~~~
树剖
说句闲话
其实就是预处理+线段树
目的：把树拆成链再用线段树处理（其实还是一种暴力，只是有点优化）
为什么不直接拆成从根节点到每一个叶子结点的链？
假如更改一个节点（有多个子节点），那么就要修改几个线段树中的值了，会影响效率
所以在这些链中不能有重叠部分
为了提高线段树的效率，我们要尽量把一条链搞长一点，而不是更多的链
所以我们就想到了下方预处理的办法
先来回顾几个问题：
1.将树从x到y结点最短路径上所有节点的值都加上z（树上差分即可）
2.求树从x到y结点最短路径上所有节点的值之和（LCA即可）
3.将以x为根节点的子树内所有节点值都加上z（dfs序+差分即可）
4.求以x为根节点的子树内所有节点值之和（同3）
但是：假如把几个问题放在一起咋做？
于是树链剖分闪亮登场
有些啥？
先说些概念
重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；
轻儿子：父亲节点中除了重儿子以外的儿子；
重边：父亲结点和重儿子连成的边；(下图加粗）
轻边：父亲节点和轻儿子连成的边；
重链：由多条重边连接而成的路径；
轻链：由多条轻边连接而成的路径；
对数组的一些解释：
| 名称 | 解释 |
|---|---|
| f[u] | 保存结点u的父亲节点 |
| dep[u] | 保存结点u的深度值 |
| size[u] | 保存以u为根的子树节点个数 |
| son[u] | 保存重儿子 |
| top[u] | 保存当前节点所在链的顶端节点（上图红点） |
| id[u] | 保存树中每个节点剖分以后的新编号（DFS的执行顺序） |
我们的目标就是把上图拆成一下几条链：
(1->4->9->13->14)
(2->6->11)
(3->7)
(5)
(8)
(10)
(12)
咋操作？
1.预处理：求f、d、size、son数组
void dfs1(int u,int fa){
f[u]=fa;
dep[u]=dep[fa]+1;
size[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
结果：
2.预处理：求出top、rk、id数组（dfs序）
void dfs2(int u,int t){
top[u]=t;
id[u]=++cnt;
a[cnt]=w[u];
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v!=son[u]&&v!=f[u])dfs2(v,v);
}
}
结果：
LCA操作咋办？有没有注意到top数组？它就是LCA中的‘跳’的变形
3.LCA
其实也可以不写
妈妈再也不用担心我不会倍增啦
这里使用了top来进行加速，因为top可以直接跳转到该重链的起始结点，轻链没有起始结点之说，他们的top就是自己。需要注意的是，每次循环只能跳一次，并且让结点深的那个来跳到top的位置，避免两个一起跳从而擦肩而过
int lca(int x,int y){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
x=f[fx],fx=top[x];
}
return dep[x]<dep[y]?x:y;
}
4.修改链
在LCA的基础上也可以这么写：
void updata_lian(int x,int y,int z){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
updata(id[fx],id[x],z,1,cnt,1);
x=f[fx],fx=top[x];
}
if(id[x]>id[y])swap(x,y);
updata(id[x],id[y],z,1,cnt,1);
}
5.计贡献
在LCA的基础上也可以这么写：
int query_lian(int x,int y){
int fx=top[x],fy=top[y],sum=0;
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
inc(sum,query(id[fx],id[x],1,cnt,1));
x=f[fx],fx=top[x];
}
if(id[x]>id[y])swap(x,y);
inc(sum,query(id[x],id[y],1,cnt,1));
return sum;
}
这样就差不多了
上题：
P3384 【模板】轻重链剖分
没什么好说的
注意一个点：mod不是题目固定的，也就是说：a[i]可能大于mod，甚至是几倍
最好双重保险，函数返回前加一个取模
出题人不要脸
#include<bits/stdc++.h>
#define ll long long
#define LC x<<1
#define RC x<<1|1
#define N 1100000
using namespace std;
ll n,m,r,mod,op,x,y,z,cnt,tot,head[N],size[N],top[N],dep[N],son[N],id[N],f[N],a[N],w[N];
struct node{
ll to,nxt;
}e[N*5];
struct nd_tree{
ll sum,lazy,len;
}t[N*5];
void inc(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
void add(ll f,ll to){
e[++tot].to=to;
e[tot].nxt=head[f];
head[f]=tot;
}
ll lca(ll x,ll y){
ll fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
x=f[fx],fx=top[x];
}
return dep[x]<dep[y]?x:y;
}
void dfs1(ll u,ll fa){
f[u]=fa;
dep[u]=dep[fa]+1;
size[u]=1;
for(ll i=head[u];i;i=e[i].nxt){
ll v=e[i].to;
if(v==fa)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(ll u,ll t){
top[u]=t;
id[u]=++cnt;
a[cnt]=w[u];
if(son[u])dfs2(son[u],t);
for(ll i=head[u];i;i=e[i].nxt){
ll v=e[i].to;
if(v!=son[u]&&v!=f[u])dfs2(v,v);
}
}
void pushup(ll x){
t[x].sum=t[LC].sum+t[RC].sum;
}
void pushdown(ll x){
if(t[x].lazy==0)return;
inc(t[LC].lazy,t[x].lazy);
inc(t[RC].lazy,t[x].lazy);
inc(t[LC].sum,t[LC].len*t[x].lazy);
inc(t[RC].sum,t[RC].len*t[x].lazy);
t[x].lazy=0;
}
void build(ll l,ll r,ll x){
t[x].len=r-l+1;
if(l==r){t[x].sum=a[l];return;}
ll mid=(l+r)>>1;
build(l,mid,LC);
build(mid+1,r,RC);
pushup(x);
}
void updata(ll ql,ll qr,ll c,ll l,ll r,ll x){
if(ql<=l&&qr>=r){
inc(t[x].sum,t[x].len*c);
inc(t[x].lazy,c);
return;
}
pushdown(x);
ll mid=(l+r)>>1;
if(ql<=mid)updata(ql,qr,c,l,mid,LC);
if(qr>mid)updata(ql,qr,c,mid+1,r,RC);
pushup(x);
}
ll query(ll ql,ll qr,ll l,ll r,ll x){
if(ql<=l&&qr>=r)return t[x].sum;
pushdown(x);
ll mid=(l+r)>>1,sum=0;
if(ql<=mid)sum+=query(ql,qr,l,mid,LC);
if(qr>mid)sum+=query(ql,qr,mid+1,r,RC);
return sum%mod;
}
void updata_lian(ll x,ll y,ll z){
ll fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
updata(id[fx],id[x],z,1,cnt,1);
x=f[fx],fx=top[x];
}
if(id[x]>id[y])swap(x,y);
updata(id[x],id[y],z,1,cnt,1);
}
ll query_lian(ll x,ll y){
ll fx=top[x],fy=top[y],sum=0;
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
inc(sum,query(id[fx],id[x],1,cnt,1));
x=f[fx],fx=top[x];
}
if(id[x]>id[y])swap(x,y);
inc(sum,query(id[x],id[y],1,cnt,1));
return sum;
}
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&r,&mod);
for(ll i=1;i<=n;i++)scanf("%lld",&w[i]),w[i]%=mod;
for(ll i=1;i<n;i++)scanf("%lld%lld",&x,&y),add(x,y),add(y,x);
dep[r]=0;f[r]=1;
dfs1(r,0);
dfs2(r,r);
build(1,n,1);
for(ll i=1;i<=m;i++){
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld%lld",&x,&y,&z);z%=mod;
updata_lian(x,y,z);
}
if(op==2){
scanf("%lld%lld",&x,&y);
printf("%lld
",query_lian(x,y));
}
if(op==3){
scanf("%lld%lld",&x,&y);y%=mod;
updata(id[x],id[x]+size[x]-1,y,1,n,1);
}
if(op==4){
scanf("%lld",&x);
printf("%lld
",query(id[x],id[x]+size[x]-1,1,n,1));
}
}
}
参考资料：https://www.cnblogs.com/ivanovcraft/p/9019090.html
https://www.cnblogs.com/lykkk/p/10183778.html（强力推荐）
猫国它不香吗
burlar就是个蜜蜂