树链剖分

题目练习：https://blog.csdn.net/qq_31908675/article/details/79991136 题目练习2：https://www.bbsmax.com/A/Vx5MRW23dN/

Tree

HDU 6547 题意：给一个带点权树，支持两种操作：修改，将链上u-v的数都开根号（下取整）；查询，查询链上u-v点权和。$a_i$<=1e9 题解：树链剖分，对于1e9，开方下取整，只要6次就变为1了。故对于修改部分，我们直接暴力修改即可，发现当前路径都是1，则不用继续修改。总体上算是树剖裸题。

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=100010; int n,q; int a[maxn];//初始点权 int wt[maxn];//新建编号点权 int cnt;//编号用的变量 int top[maxn];//所在重链的顶点编号 int id[maxn];//节点新编号 int sz[maxn];//儿子数量 int wson[maxn];//重儿子 int fa[maxn];//父节点 int deep[maxn];//深度 ll sum[maxn<<2];//线段树sum int tot,head[maxn];//前向星 struct edge{ int v,nxt; }e[maxn*2]; void init(){ memset(head,-1,sizeof(head)); for(int i=0;i<=n;i++) head[i]=-1,deep[i]=fa[i]=top[i]=id[i]=wson[i]=0; for(int i=0;i<=4*n;i++) sum[i]=0; tot=0; cnt=0;//少了这个。。 } void addedge(int u,int v){ e[tot].v=v;e[tot].nxt=head[u]; head[u]=tot++; } void dfs1(int u,int p,int d){ deep[u]=d; fa[u]=p; sz[u]=1; int mxson=-1; for(int i=head[u];~i;i=e[i].nxt){ // printf("u:%d v:%d\n") int v=e[i].v; if(v==p) continue; dfs1(v,u,d+1); sz[u]+=sz[v]; if(sz[v]>mxson) mxson=sz[v],wson[u]=v; } } void dfs2(int u,int topf){ id[u]=++cnt; wt[cnt]=a[u]; top[u]=topf; if(!wson[u]) return; dfs2(wson[u],topf); for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v; if(v==fa[u]||v==wson[u]) continue; dfs2(v,v); } } void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int rt,int l,int r){ if(l==r){ sum[rt]=wt[l];return; } int m=(l+r)>>1; build(rt<<1,l,m); build(rt<<1|1,m+1,r); pushup(rt); } void update(int rt,int l,int r,int a,int b){ if(l>=a&&r<=b&&sum[rt]==(r-l)+1) return; if(l==r){ sum[rt]=(int)sqrt(sum[rt]);return; } int m=(l+r)>>1; if(a<=m) update(rt<<1,l,m,a,b); if(m<b) update(rt<<1|1,m+1,r,a,b); pushup(rt); } ll query(int rt,int l,int r,int a,int b){ // printf("l:%d r:%d a:%d b:%d\n",l,r,a,b); if(l>=a&&r<=b) return sum[rt]; int m=(l+r)>>1; ll ans=0; if(a<=m) ans+=query(rt<<1,l,m,a,b); if(m<b) ans+=query(rt<<1|1,m+1,r,a,b); return ans; } void uprange(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]]) swap(x,y); update(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); update(1,1,n,id[x],id[y]); } ll qrange(int x,int y){ ll ans=0; while(top[x]!=top[y]){ // printf("x:%d y:%d\n",x,y);// if(deep[top[x]]<deep[top[y]]) swap(x,y); ans+=query(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); ans+=query(1,1,n,id[x],id[y]); return ans; } void test(){ int h=1000000000; while(h!=1){ printf("%d ",h); h=(int)sqrt(h); } printf("1\n"); } int main(){ //test(); while(~scanf("%d%d",&n,&q)){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); int op,u,v; init(); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); addedge(u,v);addedge(v,u); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); // puts("init successfully"); for(int i=1;i<=q;i++){ scanf("%d%d%d",&op,&u,&v); if(!op){ uprange(u,v); }else{ printf("%I64d\n",qrange(u,v)); } } } return 0; }

Water Tree

CF 343D 题意给定一颗树，初始每个点为空。3种操作。op=1，将x及其所在子树点权更新为1；op==0，将x及其所有祖先点权更新为0；op=3，查询当前点x是否为1。 题解：树剖，更新x所在子树时，注意编号是$id[x]$到$id[x]+sz[x]-1$.

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=500010; int n,q; int wt[maxn];//新建编号点权 int cnt;//编号用的变量 int top[maxn];//所在重链的顶点编号 int id[maxn];//节点新编号 int sz[maxn];//儿子数量 int wson[maxn];//重儿子 int fa[maxn];//父节点 int deep[maxn];//深度 int sum[maxn<<2],lazy[maxn<<2];//线段树sum int tot,head[maxn];//前向星 struct edge{ int v,nxt; }e[maxn*2]; void init(){ memset(head,-1,sizeof(head)); for(int i=0;i<=n;i++) head[i]=-1,deep[i]=fa[i]=top[i]=id[i]=wson[i]=0; for(int i=0;i<=4*n;i++) sum[i]=0,lazy[i]=-1; tot=0; cnt=0;//少了这个。。 } void addedge(int u,int v){ e[tot].v=v;e[tot].nxt=head[u]; head[u]=tot++; } void dfs1(int u,int p,int d){ deep[u]=d; fa[u]=p; sz[u]=1; int mxson=-1; for(int i=head[u];~i;i=e[i].nxt){ // printf("u:%d v:%d\n") int v=e[i].v; if(v==p) continue; dfs1(v,u,d+1); sz[u]+=sz[v]; if(sz[v]>mxson) mxson=sz[v],wson[u]=v; } } void dfs2(int u,int topf){ id[u]=++cnt; wt[cnt]=0; top[u]=topf; if(!wson[u]) return; dfs2(wson[u],topf); for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v; if(v==fa[u]||v==wson[u]) continue; dfs2(v,v); } } void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void pushdown(int rt,int l,int r){ int m=(l+r)>>1; lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; sum[rt<<1]=(m-l+1)*lazy[rt]; sum[rt<<1|1]=(r-m)*lazy[rt]; lazy[rt]=-1; } void build(int rt,int l,int r){ if(l==r){ sum[rt]=0;return; } int m=(l+r)>>1; build(rt<<1,l,m); build(rt<<1|1,m+1,r); pushup(rt); } void update(int rt,int l,int r,int a,int b,int val){ if(l>=a&&r<=b){ sum[rt]=(r-l+1)*val; lazy[rt]=val;//覆盖 return; } if(lazy[rt]!=-1) pushdown(rt,l,r); int m=(l+r)>>1; if(a<=m) update(rt<<1,l,m,a,b,val); if(m<b) update(rt<<1|1,m+1,r,a,b,val); pushup(rt); } int query(int rt,int l,int r,int pos){ if(l==r) return sum[rt]; if(lazy[rt]!=-1) pushdown(rt,l,r); int m=(l+r)>>1; if(pos<=m) return query(rt<<1,l,m,pos); return query(rt<<1|1,m+1,r,pos); } void Add(int x){ // update(1,1,n,id[x],id[x]+sz[x],1); update(1,1,n,id[x],id[x]+sz[x]-1,1); } void Sub(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]]) swap(x,y); update(1,1,n,id[top[x]],id[x],0); x=fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); update(1,1,n,id[x],id[y],0); } int Que(int x){ return query(1,1,n,id[x]); } int main(){ while(~scanf("%d",&n)){ int op,u,v; init(); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); addedge(u,v);addedge(v,u); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); // puts("init successfully"); scanf("%d",&q); for(int i=1;i<=q;i++){ scanf("%d%d",&op,&u); if(op==1){ Add(u); }else if(op==2){ Sub(u,1); }else{ printf("%d\n",Que(u)); } } } return 0; }

月下”毛景树”(边权树剖)

p4315 题目链接：https://www.luogu.org/problem/P4315 未完待续（咕咕咕。。