树链剖分：

树上操作并不能实现一段链的直接更新。

树链剖分就解决了这个问题。

本质上是树形到线性的转化。

通过子树，重链是一个连续的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
      
       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
       
        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 dfnvoid 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) 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
         
          dep[y]) swap(x,y);    return x;}void wrk1(int x,int y,ll z){    while(top[x]!=top[y]){        if(dep[top[x]]
          
           >1;            int ss=er[x][mm];            if(dfn[ss]<=dfn[nrt]&&dfn[nrt]<=dfn2[ss]){                in=ss;break;            }            else if(dfn[nrt]
          
         
        
       
      

 

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
      
       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
       
        >1);    if(L<=mid) ret+=query(ls,l,mid,L,R);    if(mid
        

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