树链剖分

树链剖分是搞啥的？

一种类似于原子崩坏的超能力。

先把树炸成好多好多条链。然后把这些链组装起来，以进行路径修改，路径查询。

几个概念

• 重儿子，轻儿子
• 轻边
• 重边，重链

请尽情发挥艺术天赋，动手画棵树。

两个看起来没什么用的事实

• v是u的一个轻儿子: size[v]*2 < size[u]

• 在DFS的时候，如果我们先采访重儿子，那么重链的DFS序连续。

一个看起来还是没什么用的事实

x到根的路径中，重链,轻边的条数都是log(n)级别的

假的证明：

我们从x向根节点走。

根据上面那条性质: 树的总结点个数 <= pow(2, x到根，轻边的个数)

所以x到根路径上，轻边的条树，是log级别的。

而，两条重链之间，至少有一条轻边。所以重链的条数，也是log级别的。

似乎还是有那么一点点用的

推广一下上面的结论。

( ⊙ o ⊙ )！任意两点之间的路径，重链,轻边的条数都是log(n)级别的哎！

只要我们要维护的信息满足区间可合并【区间最值，区间和，区间GCD】

我们就可以把一条链，分成log条。

又每一条链DFS序连续。因此我们可以用线段树维护每一条链。

---

容易搞错的地方

• dfn[x]与x区分开、
• 在找两个点的LCA的时候，top深度高的先往上爬。

几个栗子

POJ3237

题意：区间更新，区间取反，区间最值

我发明了一种神妙的战法。在push_up的时候把懒惰标记也传上去了。

调代码的时候，

WA! 懒惰标记上天啦！

我的内心是崩溃的.....

所以，我是来搞笑的吗？

code

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef pair
       
         pii;const int N = 200000+10;const int INF = 1e9+7;vector
        
          g[N];int edge_id[N];int size[N];int dep[N];int son[N], par[N], dis[N];int dfn[N], moment, who[N];int top[N];int T, n;int u[N], v[N], w[N];void init() {    moment = 0;    for(int i=0;i
         
           maxSize) maxSize = size[v], id = v; } son[u] = id;}void dfs(int u,int p) { dfn[u] = ++moment; who[moment] = u; top[u] = p; //printf("u = %d, p = %d \n", u, p); if (son[u] != -1) { //printf("%d -> %d\n",u, son[u]); dfs(son[u], p); } for(int i=0;i
          
           >1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); nod[rt] = nod[rt<<1] + nod[rt<<1|1];}void push_down(int rt) { if (nod[rt].ne) { //printf("##### rt = %d\n", rt); nod[rt<<1].mx = -nod[rt<<1].mx; nod[rt<<1].mn = -nod[rt<<1].mn; swap(nod[rt<<1].mx, nod[rt<<1].mn); nod[rt<<1|1].mx = -nod[rt<<1|1].mx; nod[rt<<1|1].mn = -nod[rt<<1|1].mn; swap(nod[rt<<1|1].mx, nod[rt<<1|1].mn); nod[rt<<1].ne ^= 1; nod[rt<<1|1].ne ^= 1; nod[rt].ne = 0; }}int query(int l,int r,int rt,int L,int R) { //printf("gg\n"); //printf("! %d %d %d %d\n", l,r,L,R); if (L<=l&&r<=R) { //printf("rt=%d, [%d, %d] mx=%d\n", rt,l,r,nod[rt].mx); return nod[rt].mx; } //if (rt!=8) push_down(rt); int mid = (l+r)>>1; int ans = - INF; if (L <= mid) ans = query(l,mid,rt<<1,L,R); if (R > mid) ans = max(ans, query(mid+1,r,rt<<1|1,L,R)); //printf("%d %d %d %d %d\n", l,r,L,R,ans); return ans; }void update(int l,int r,int rt,int pos,int x) { if (l == r) { nod[rt].mx = nod[rt].mn = x; nod[rt].ne = 0; return; } //if (rt!=8) push_down(rt); int mid = (l+r)>>1; if (pos <= mid) update(l,mid,rt<<1,pos,x); else update(mid+1,r,rt<<1|1,pos,x); nod[rt] = nod[rt<<1] + nod[rt<<1|1];}void neg_update(int l,int r,int rt,int L,int R) { //printf("%d %d %d %d\n", l,r, L,R); if (L<=l&&r<=R) { nod[rt].ne ^= 1; nod[rt].mn *= -1; nod[rt].mx *= -1; //printf("rt=%d [%d, %d] %d %d, ne=%d\n", rt,nod[rt].l, nod[rt].r, nod[rt].mn, nod[rt].mx, nod[rt].ne); swap(nod[rt].mn, nod[rt].mx); return; } //if(rt!=8) push_down(rt); int mid = (l+r)>>1; if (L <= mid) neg_update(l,mid,rt<<1,L,R); if (R > mid) neg_update(mid+1,r,rt<<1|1,L,R); nod[rt] = nod[rt<<1] + nod[rt<<1|1];}int max_on_path(int u, int v) { int ans = - INF; int f1 = top[u], f2 = top[v]; while (f1 != f2) { //printf("%d %d\n", f1, f2); if (dep[f1] < dep[f2]) { swap(f1, f2); swap(u, v); } //printf("[%d, %d]\n", dfn[f1], dfn[u]); ans = max(ans, query(1,n,1,dfn[f1],dfn[u])); //printf("%d\n", ans); u = par[f1]; f1 = top[u]; //printf("%d %d %d\n", u, f1, f2); } if (u == v) return ans; if (dep[u] > dep[v]) swap(u, v); ans = max(ans, query(1,n,1,dfn[son[u]],dfn[v])); return ans;}void update_on_tree(int u, int v) { int f1 = top[u], f2 = top[v]; while (f1 != f2) { if (dep[f1] < dep[f2]) { swap(f1, f2); swap(u, v); } neg_update(1,n,1,dfn[f1],dfn[u]); u = par[f1]; f1 = top[u]; } if (u == v) return; if (dep[u] > dep[v]) swap(u, v); neg_update(1,n,1,dfn[son[u]], dfn[v]);}int main() { scanf("%d", &T); while (T --) { scanf("%d", &n); init(); for (int i=1;i
          
         
        
       
      
     
    

Gym 101741 C

题意

给出一棵树，与m条路径，选出最小的点集，使得每条路径都包含点集中的点。

做法

• 在一条链上，就是个按右端点排序的贪心。

• 把路径按照LCA的深度从高到低排序。

• 然后遍历所有路径，如果路径上没有选择的点，那就选择LCA。否则，什么都不做。这个可以通过单点更新，区间查询来实现。

code

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N = 400000+10;int n;int son[N],size[N],par[N],top[N],dep[N];int dfn[N],who[N],moment;vector
       
         g[N];void preSovle(int u,int p) {    size[u]=1;    par[u] =p;    dep[u] =dep[p]+1;    int mx=0, bst=-1;    for(int i=0;i
        
          mx) {            mx = size[v];            bst = v;        }    }    son[u] = bst;}void dfs(int u,int p) {    top[u]=p;    dfn[u]=++moment;    who[moment]=u;    if(son[u]!=-1){        dfs(son[u],p);    }    for(int i=0;i
         
           dep[o.lca]; }} q[N];int sum[N<<2];void update(int l,int r,int rt,int pos){ if(l==r) { sum[rt] ++; return; } int mid=(l+r)>>1; if (pos<=mid) update(l,mid,rt<<1,pos); else update(mid+1,r,rt<<1|1,pos); sum[rt]=sum[rt<<1]+sum[rt<<1|1];}int query(int l,int r,int rt,int L,int R){ if(L<=l&&r<=R) { return sum[rt]; } int mid=(l+r)>>1; int ans=0; if(L<=mid) ans+=query(l,mid,rt<<1,L,R); if(R >mid) ans+=query(mid+1,r,rt<<1|1,L,R); return ans;}pair
          
            sum_path(int u,int v) { // (lca, sum) int f1=top[u], f2=top[v]; int ans=0; while(f1!=f2) { //printf("%d %d\n", f1, f2); if (dep[f1] < dep[f2]) { swap(f1,f2); swap(u,v); } ans+=query(1,n,1,dfn[f1],dfn[u]); u=par[f1], f1=top[u]; //printf("%d %d\n", f1, f2); } if(dep[u]>dep[v]) swap(u,v); ans+=query(1,n,1,dfn[u],dfn[v]); return make_pair(u, ans);}int main() { scanf("%d",&n); for(int i=1;i