思路很简单,但非常考验代码能力
思路
假设对区间[2,8]进行操作
路径由lca 15分成左右俩条链。将左端点2跳到最右上17,对左链17-16-10-15上每个作为左儿子的节点的兄弟操作。
于是构造新树:节点的新父亲为最近异侧祖先的同侧儿子
(手画略丑请忽略)
链上区间操作——树链剖分
一共有三棵树:题目所给原树,构造新树,树链剖分所用线段树
来整合一下需要的操作,便于理清代码思路,并代替行间注释
1、dfs()遍历原树 cnt[]子树所含叶子数,即节点包含区间长度 dep[]深度 Fa[][]倍增求lca
2、Do()连边构造新树
3、树链剖分fhe() Son[]重儿子 siz[]新树子树大小 fa[]新树父亲
che() s[]新树cnt前缀和 dfn[] top[]
4、操作
getlca()
L,R跳到同侧最高
如果L,R都在lca之上,对lca操作,return
如果L在lca之上,对lca左儿子操作,return
树剖[L,lca右儿子)
代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; const int MAX=1e6+10; #define int long long int n,q,x,y,d,op,fa[MAX],son[MAX][2],rt,bro[MAX]; int cnt[MAX],s[MAX]; int Son[MAX],siz[MAX],dfn[MAX],chuo,top[MAX],dep[MAX],Fa[MAX][20]; vector<int>g[MAX]; struct node{ int sum,laz; } t[MAX<<1]; inline int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } void dfs(int,int); void Do(int,int,int); inline int getlca(int,int); void fhe(int,int); void che(int,int); inline void add(int,int,int,int); inline int ask(int,int,int); void update(int,int,int,int,int,int); int query(int,int,int,int,int); inline void pushdown(int,int,int); signed main(){ n=read();q=read(); for(int i=1+n;i<2*n;++i){ son[i][0]=read();son[i][1]=read(); bro[son[i][0]]=son[i][1];bro[son[i][1]]=son[i][0]; }for(int i=n+1;i<2*n;++i) if(!bro[i]){rt=i;break;} son[0][0]=son[0][1]=rt;bro[rt]=rt; dfs(rt,rt);Do(rt,0,0);Do(rt,0,1); fhe(rt,rt);che(rt,rt); for(int i=2;i<=chuo;++i) s[i]+=s[i-1]; while(q--){ op=read();x=read();y=read(); int lca=getlca(x,y);// if(x==son[Fa[x][0]][0]) x=bro[fa[x]]; if(y==son[Fa[y][0]][1]) y=bro[fa[y]]; if(op==1){ d=read(); if(dep[x]<=dep[lca]&&dep[y]<=dep[lca]){ update(1,1,2*n-1,dfn[lca],dfn[lca],d);continue; }add(x,lca,d,0);add(y,lca,d,1); }else{ if(dep[x]<=dep[lca]&&dep[y]<=dep[lca]){ printf("%lld\n",query(1,1,2*n-1,dfn[lca],dfn[lca])); continue; }printf("%lld\n",ask(x,lca,0)+ask(y,lca,1)); } } } void dfs(int u,int f){ dep[u]=dep[f]+1;Fa[u][0]=f; for(int i=1;(1<<i)<=dep[u];++i) Fa[u][i]=Fa[Fa[u][i-1]][i-1]; if(!son[u][0]){cnt[u]=1;return;} dfs(son[u][0],u);dfs(son[u][1],u); cnt[u]=cnt[son[u][0]]+cnt[son[u][1]]; }void Do(int u,int x,int p){ if(!u) return; if(u==son[Fa[u][0]][p]) g[son[x][p]].push_back(u); Do(son[u][p],x,p);Do(son[u][p^1],u,p); }inline int getlca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); int h=dep[x]-dep[y]; for(int i=0;i<20;++i) if(h&(1<<i)) x=Fa[x][i]; if(x==y) return x; for(int i=19;i>=0;--i) if(Fa[x][i]!=Fa[y][i]){ x=Fa[x][i];y=Fa[y][i]; } return Fa[x][0]; } void fhe(int u,int f){ fa[u]=f;siz[u]=1; for(int i=0;i<g[u].size();++i){ int v=g[u][i]; fhe(v,u);siz[u]+=siz[v]; if(siz[Son[u]]<siz[v]) Son[u]=v; } }void che(int u,int ance){ dfn[u]=++chuo;top[u]=ance;s[chuo]=cnt[u]; if(Son[u]) che(Son[u],ance); for(int i=0;i<g[u].size();++i) if(g[u][i]!=Son[u]) che(g[u][i],g[u][i]); }inline void add(int x,int y,int num,int p){ if(dep[x]<=dep[y]){ update(1,1,2*n-1,dfn[son[y][p]],dfn[son[y][p]],num); return; }y=son[y][p^1]; while(top[x]!=top[y]){ update(1,1,2*n-1,dfn[top[x]],dfn[x],num); x=fa[top[x]]; }update(1,1,2*n-1,dfn[y]+1,dfn[x],num); }inline int ask(int x,int y,int p){ if(dep[x]<=dep[y]) return query(1,1,2*n-1,dfn[son[y][p]],dfn[son[y][p]]); y=son[y][p^1];int ans=0; while(top[x]!=top[y]){ ans+=query(1,1,2*n-1,dfn[top[x]],dfn[x]); x=fa[top[x]]; }ans+=query(1,1,2*n-1,dfn[y]+1,dfn[x]); return ans; } void update(int pos,int l,int r,int ll,int rr,int d){ if(l>=ll&&r<=rr){ t[pos].sum+=(s[r]-s[l-1])*d; t[pos].laz+=d;return;// }int mid=l+r>>1;pushdown(pos,s[mid]-s[l-1],s[r]-s[mid]); if(mid>=ll) update(pos<<1,l,mid,ll,rr,d); if(mid<rr) update(pos<<1|1,mid+1,r,ll,rr,d); t[pos].sum=t[pos<<1].sum+t[pos<<1|1].sum; }int query(int pos,int l,int r,int ll,int rr){ if(l>rr||r<ll) return 0; if(l>=ll&&r<=rr) return t[pos].sum; int mid=l+r>>1;pushdown(pos,s[mid]-s[l-1],s[r]-s[mid]); return query(pos<<1,l,mid,ll,rr)+query(pos<<1|1,mid+1,r,ll,rr); }inline void pushdown(int pos,int l1,int l2){ if(t[pos].laz){ t[pos<<1].sum+=l1*t[pos].laz;t[pos<<1|1].sum+=l2*t[pos].laz; t[pos<<1].laz+=t[pos].laz;t[pos<<1|1].laz+=t[pos].laz; t[pos].laz=0; } }View Code
因为线段树懒标记没有+=,调了一下午,原地去世
标签:新树,鸽子,int,MAX,门外,mid,Fa,lca,树上 From: https://www.cnblogs.com/yswn/p/17575955.html