树链剖分：
树上操作并不能实现一段链的直接更新。
树链剖分就解决了这个问题。
本质上是树形到线性的转化。
通过子树，重链是一个连续的dfn区间的优秀性质，可以在dfn序列上进行操作，达到在树上操作的目的。
通常和线段树结合。
板子：以前写的。
树链剖分
例题：
1.遥远的国度
题目大意：
给定一棵有根树，每个点有一个权值，提供三种操作：
1.将x节点变为根节点
2.将x到y路径上的点的权值全部改为v
3.询问x的子树中点权的最小值
如果根不变，那么2、3就直接做了。
但是根变化了，随之第三问，子树就变化了。
每次重建dfn序列显然是爆炸的。
所以，就考虑让树形态根一直保持原来的不变。
每次第三问，就考虑当前的新的根对这个点子树的影响。
讨论一下：
分成三种情况
1.new root = xx 整个子树的min就是ans
2. lca(new root,xx) !=xx 没有影响，直接求。
3. lca(new root,xx) =xx 找一下root在xx的哪个子树里 这个子树的补集就是解了
注意是补集，因为树的父子关系完全颠倒了。但是只有这个子树成立，别的子树还是xx的子树。（画图理解下）
代码：（luoguAC，bzoj WA ????!!??!!??!）(对拍也没找到错)
注意，树剖lca，最后要考虑swap(x,y),返回浅的。
#include<bits/stdc++.h> using namespace std; const int N=100000+10; typedef long long ll; const ll inf=(ll)21474836480; int n,m; int root; int nrt; vector<int>er[N]; struct node{ int nxt,to; }e[N*2]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } int w[N]; int top[N],son[N],siz[N],dfn[N],dfn2[N],fdfn[N],fa[N]; int dep[N]; int tot;//number of dfn void dfs1(int x,int d){ siz[x]=1; dep[x]=d; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y!=fa[x]){ fa[y]=x; dfs1(y,d+1); if(siz[y]>siz[son[x]]){ son[x]=y; } siz[x]+=siz[y]; } } } void dfs2(int x){ dfn[x]=++tot; fdfn[tot]=x; if(!top[x]) top[x]=x; if(son[x]) er[x].push_back(son[x]),top[son[x]]=top[x],dfs2(son[x]); for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y!=fa[x]&&y!=son[x]){ er[x].push_back(y); dfs2(y); } } dfn2[x]=tot; } struct tr{ ll mi,ch; #define m(x) t[x].mi #define c(x) t[x].ch #define ls (x<<1) #define rs (x<<1|1) #define mid (l+r>>1) }t[4*N]; void pushup(int x){ m(x)=min(m(ls),m(rs)); } void pushdown(int x){ if(c(x)==-1) return; c(ls)=c(x);m(ls)=c(x); c(rs)=c(x);m(rs)=c(x); c(x)=-1; } void build(int x,int l,int r){ if(l==r){ m(x)=w[fdfn[l]];c(x)=-1; return; } m(x)=inf;c(x)=-1; build(ls,l,mid);build(rs,mid+1,r); pushup(x); } void chan(int x,int l,int r,int L,int R,ll k){ if(L<=l&&r<=R){ c(x)=k;m(x)=k;return; } pushdown(x); if(L<=mid) chan(ls,l,mid,L,R,k); if(mid<R) chan(rs,mid+1,r,L,R,k); pushup(x); } ll query(int x,int l,int r,int L,int R){ if(L>R) return inf; if(L<=l&&r<=R){ return m(x); } pushdown(x);ll ret=inf; if(L<=mid) ret=min(ret,query(ls,l,mid,L,R)); if(mid<R) ret=min(ret,query(rs,mid+1,r,L,R)); return ret; } int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); return x; } void wrk1(int x,int y,ll z){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); chan(1,1,n,dfn[top[x]],dfn[x],z); x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y); chan(1,1,n,dfn[y],dfn[x],z); } ll wrk2(int x){ if(x==nrt){ return query(1,1,n,1,n); } int anc=lca(x,nrt); if(anc==x){ int ll=0,rr=er[x].size()-1; int in; while(ll<=rr){ int mm=(ll+rr)>>1; int ss=er[x][mm]; if(dfn[ss]<=dfn[nrt]&&dfn[nrt]<=dfn2[ss]){ in=ss;break; } else if(dfn[nrt]<dfn[ss]) rr=mm-1; else ll=mm+1; } return min(query(1,1,n,1,dfn[in]-1),query(1,1,n,dfn2[in]+1,n)); } else return query(1,1,n,dfn[x],dfn2[x]); } int main() { scanf("%d%d",&n,&m);int x,y; for(int i=1;i<=n-1;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x); for(int i=1;i<=n;i++) scanf("%d",&w[i]); scanf("%d",&root); nrt=root; dfs1(root,1); dfs2(root); build(1,1,n); int op; ll z; while(m--){ scanf("%d",&op); if(op==1){ scanf("%d",&nrt); } else if(op==2){ scanf("%d%d%d",&x,&y,&z); wrk1(x,y,z); } else if(op==3){ scanf("%d",&x); printf("%lld ",wrk2(x)); } } return 0; }
2.
[LNOI2014]LCA
题意：
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。
一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。 （即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）
题解：
很巧妙的方法。
直接暴力肯定tle
对于z，可以暴力往上打标记，一直到根，对于[l,r]的数，分别往上找到的第一个标记点就是lca。
发现，lca的深度就是到根的点数。所以，如果把从z到根的路径上的点权++，那么，l,r中的i和z的lca的深度，就是i到根节点的路径上的点权和。
发现，这个结论是可逆的。就是说，如果把所有i到根节点的路径++，那么，z到根节点的路径上的值，就是这次查询的结果！！！
这样子复杂度并没有降下来。
我们转化成差分:对于一个询问，分成:[1,r] - [1,l-1]两个部分求解。
而，我们再用一个离线操作，就是把每个1~n的数，记录一下，是哪个询问的l-1或者是r
那么，我们从i=1开始更新到根的路径上的值，每次将与i有关的询问，处理一下这个询问[1,r]或者[1,l-1]的值。
最后统计做差即可。
代码：（脑残了pushdown竟然忘了s(ls)+=a(x)*(len)忘了乘区间长度。。。而且，，，add懒标记忘了下放！！！）
（心急不得啊。）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50000+10; const int mod=201314; int n,m; struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } int fa[N],top[N],son[N],dfn[N],dep[N]; int sz[N]; void dfs(int x,int d){ sz[x]=1;dep[x]=d; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y!=fa[x]){ fa[y]=x; dfs(y,d+1); sz[x]+=sz[y]; if(sz[y]>sz[son[x]]){ son[x]=y; } } } } int tot; void dfs2(int x){ dfn[x]=++tot; if(!top[x]) top[x]=x; if(son[x]) top[son[x]]=top[x],dfs2(son[x]); for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x]||y==son[x]) continue; dfs2(y); } } struct tr{ ll sum; ll ad; #define ls x<<1 #define rs x<<1|1 #define s(x) t[x].sum #define a(x) t[x].ad }t[4*N]; void build(int x,int l,int r){ if(l==r){ a(x)=0; s(x)=0;return; } s(x)=0;a(x)=0;int mid=(l+r>>1); build(ls,l,mid); build(rs,mid+1,r); s(x)=s(ls)+s(rs); } void pd(int x,int l,int r){ if(!a(x)) return; int mid=l+r>>1; s(ls)=(s(ls)+a(x)*(mid-l+1))%mod; s(rs)=(s(rs)+a(x)*(r-mid))%mod; a(ls)=(a(ls)+a(x))%mod; a(rs)=(a(rs)+a(x))%mod; a(x)=0; } void upda(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ a(x)++;s(x)+=r-l+1; a(x)%=mod;s(x)%=mod; return; } int mid=(l+r>>1); pd(x,l,r); if(L<=mid) upda(ls,l,mid,L,R); if(mid<R) upda(rs,mid+1,r,L,R); s(x)=(s(ls)+s(rs))%mod; } ll query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R) return s(x); pd(x,l,r); ll ret=0;int mid=(l+r>>1); if(L<=mid) ret+=query(ls,l,mid,L,R); if(mid<R) ret+=query(rs,mid+1,r,L,R); ret%=mod; return ret; } struct que{ ll lans,rans; int x; int l,r; }qus[N]; vector<int>q[N]; void wrk1(int x){ while(top[x]!=1){ upda(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } upda(1,1,n,1,dfn[x]); } ll wrk2(int x){ ll ret=0; while(top[x]!=1){ ret+=query(1,1,n,dfn[top[x]],dfn[x]); ret%=mod; x=fa[top[x]]; } ret=(ret+query(1,1,n,1,dfn[x]))%mod; return ret; } int main() { scanf("%d%d",&n,&m); int x,y; for(int i=2;i<=n;i++){ scanf("%d",&x);x++; add(i,x);add(x,i); } int l,r; for(int i=1;i<=m;i++){ scanf("%d%d%d",&l,&r,&qus[i].x); l++,r++,qus[i].x++; q[l-1].push_back(i); q[r].push_back(i); qus[i].l=l;qus[i].r=r; } dfs(1,1); dfs2(1); build(1,1,n); for(int i=1;i<=n;i++){ wrk1(i); for(int j=0;j<q[i].size();j++){ int id=q[i][j];; ll sum=wrk2(qus[id].x); if(qus[id].l-1==i) qus[id].lans=sum; else qus[id].rans=sum; } } for(int i=1;i<=m;i++){ printf("%d ",(qus[i].rans+mod-qus[i].lans)%mod); } return 0; }
强制在线？：
可持久化扫描线。可持久化线段树进行区间加法。空间log^2
PS：还可以线段树分治+虚树的离线做法
upda:2019.5.7
加强版：
k次方？
理解路径+1的本质：把整个的距离差分成了每一步的距离 ！(dep[x]+1)^1-dep[x]^1=1
把1换成k即可。这样每个点有一个权值，还有一个标记的贡献次数。线段树维护即可
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=50005; const int mod=998244353; int n,m,k; int ad(int x,int y){ return x+y>=mod?x+y-mod:x+y; } int mul(int x,int y){ return (ll)x*y%mod; } int qm(int x,int y){ int ret=1; while(y){ if(y&1) ret=(ll)ret*x%mod; x=(ll)x*x%mod; y>>=1; } return ret; } struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y;hd[x]=cnt; } int fa[N],top[N],son[N],sz[N],dep[N]; ll val[N]; void dfs(int x,int d){ dep[x]=d; val[x]=ad(qm(d,k),mod-qm(d-1,k)); sz[x]=1; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; fa[y]=x; dfs(y,d+1); sz[x]+=sz[y]; if(sz[y]>sz[son[x]]) son[x]=y; } } int dfn[N],fdfn[N],df; void dfs2(int x){ dfn[x]=++df;fdfn[df]=x; if(!top[x]) top[x]=x; if(son[x]) top[son[x]]=top[x],dfs2(son[x]); for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==son[x]) continue; dfs2(y); } } struct tr{ int add; int tot,sum; }t[4*N]; #define ls (x<<1) #define rs (x<<1|1) #define mid ((l+r)>>1) void pushup(int x){ t[x].sum=ad(t[ls].sum,t[rs].sum); } void build(int x,int l,int r){ if(l==r){ t[x].tot=val[fdfn[l]];return; } build(ls,l,mid);build(rs,mid+1,r); t[x].tot=ad(t[ls].tot,t[rs].tot); } void tag(int x,int l,int r,int c){ t[x].sum=ad(t[x].sum,mul(t[x].tot,c)); t[x].add=ad(t[x].add,c); } void pushdown(int x,int l,int r){ if(!t[x].add) return; tag(ls,l,mid,t[x].add); tag(rs,mid+1,r,t[x].add); t[x].add=0; } void chan(int x,int l,int r,int L,int R,int c){ if(L<=l&&r<=R){ tag(x,l,r,c);return; } pushdown(x,l,r); if(L<=mid) chan(ls,l,mid,L,R,c); if(mid<R) chan(rs,mid+1,r,L,R,c); pushup(x); } int query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R) return t[x].sum; pushdown(x,l,r); if(L>mid) return query(rs,mid+1,r,L,R); if(R<=mid) return query(ls,l,mid,L,R); return ad(query(rs,mid+1,r,L,R),query(ls,l,mid,L,R)); } void wrk1(int x){ while(x){ chan(1,1,n,dfn[top[x]],dfn[x],1); x=fa[top[x]]; } } int wrk2(int x){ int ret=0; while(x){ ret=ad(ret,query(1,1,n,dfn[top[x]],dfn[x])); x=fa[top[x]]; } return ret; } struct qs{ int id,pos,x; bool friend operator <(qs a,qs b){ return a.pos<b.pos; } }q[N]; int ans[N]; int main(){ rd(n);rd(m);rd(k); int y; for(reg i=2;i<=n;++i){ rd(y);add(y,i); } dfs(1,1);dfs2(1); // prt(dfn,1,n); // prt(fa,1,n); // prt(top,1,n); // prt(son,1,n); // prt(fdfn,1,n); // prt(val,1,n); build(1,1,n); for(reg i=1;i<=m;++i){ rd(q[i].pos);rd(q[i].x);q[i].id=i; } sort(q+1,q+m+1); int ptr=0; for(reg i=1;i<=n;++i){ wrk1(i); while(ptr<m&&q[ptr+1].pos==i){ ++ptr; ans[q[ptr].id]=wrk2(q[ptr].x); } } for(reg i=1;i<=m;++i){ printf("%d ",ans[i]); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */