---
title: 輕重鍊剖分
tags: 7th 教學
slideOptions:
theme: black
transition: 'slide'
---
# 輕重鍊剖分
#### Author:H1de_on_bruH
## 路徑問題:

假設有個節點為$N$個的樹 每個節點上都有一個點權 有$Q$次詢問 每次詢問$u$跟$v$路徑上所有點的權和
且$N,Q\le 10^5$，我們該怎麼在一秒內執行完?

### LCA
我們可以用倍增法先$O(N\log N)$預處理 每次詢問花$O(\log N)$查詢
這樣總體的複雜度是$O((N+Q)\log N)$ 在這樣的資料範圍下可以很漂亮的解決這個問題

## 動態路徑問題

跟剛剛的情境完全一樣 只是我們在詢問的時候多加了一個動作 `修改節點權值`
那麼倍增法就毫無用武之地了 每次修改都要花$O(N\log N)$

**倍增法:完敗\\|/**

## 輕重鍊剖分 aka 樹鍊剖分
想像一下 我們把這棵樹分割成一條一條的鍊
如果鍊條少一點 我們就可以在鍊上套BIT、線段數等資料結構
讓他在複雜度不會爛掉的情況下維護節點權值

那到底怎麼切 才會是最好的呢?
我們先定義一些名詞

`重兒子:表示在所有子節點中 擁有的子節點樹最多的那一個`
`重邊:由該節點連到他的重兒子的那個邊就叫重邊`
`輕兒子:除了重兒子以外的其他節點`
`輕邊:連到輕兒子的邊`

我們一開始切這棵樹時 從根開始往下走 直接走向重兒子
這樣子走到底後就會有一條鍊 那其他剩下來的子樹再做一樣的事
這樣子就可以把這棵樹分成一條一條的鍊

至於為甚麼這樣會是好的
因為每次往輕邊走後子樹的大小必定$\le$原來的$\frac{1}{2}$
從任兩點的LCA分兩邊往下走只需要走過$O(\log N)$條
所以查詢路徑和的複雜度為$O(\log^2 N)$

### 樹鍊剖分的實現

vector<int>path[N];
int son[N],num[N],p[N],dep[N],top[N],dfn[N],cnt;
void dfs1(int now)
{
    son[now]=-1;
    num[now]=1;
    for(int i:path[now])
    {
        if(!dep[i])
        {
            dep[i]=dep[now]+1;
            p[i]=now;
            dfs1(i);
            num[now]+=num[i];
            if(son[now]==-1||num[i]>num[son[now]])son[now]=i;
        }
    }
}

我們先尋訪一次這棵樹 把上面各個節點的子樹大小、重兒子、深度等算出來
然後第二次尋訪時構造出鍊 並把鍊上的點編號打好

int cnt=0;
void dfs2(int now,int t)
{
    top[now]=t;//標示鍊的頂端的節點
    cnt++;
    dfn[now]=cnt;//表示該節點在鍊上的編號
    if(son[now]==-1)return;
    dfs2(son[now],now);
    for(int i:path[now])
        if(i!=p[now]&&i!=son[now])
            dfs2(i,i);
}

這樣我們就成功的用c++切開這棵樹了~~

## 例題:
### [LibreOJ #10138](https://loj.ac/p/10138)
經典的樹剖題 直接開一棵線段樹就可以應付了
查詢的核心就是每次要找深度最深的那個點 讓他往最頂跳
跳到最頂時把路徑上的和加起來
那直到兩個點都在同一條鍊時 就把兩個點之間的值加起來 就會是答案了
最大值的做法也相同

:::spoiler sample code

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define FOR(i,x,y) for(int i=x;i<y;i++)
#define INF 1e16
#define Yuubari_chan_kawaii ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=2e5+5;
int n,dfn[N],son[N],top[N],num[N],dep[N],p[N];
vector<int>path[N];
struct node
{
     int mx,sum;
}seg[N<<2];
void update(int x,int l,int r,int qx,int val)
{
     if(l==r)
     {
          seg[x].mx=seg[x].sum=val;
          return;
     }
     int mid=(l+r)>>1;
     if(qx<=mid)update(x<<1,l,mid,qx,val);
     else update(x<<1|1,mid+1,r,qx,val);
     seg[x].mx=max(seg[x<<1].mx,seg[x<<1|1].mx);
     seg[x].sum=seg[x<<1].sum+seg[x<<1|1].sum;
}
int big(int x,int l,int r,int ql,int qr)
{
     if(ql<=l&&r<=qr)return seg[x].mx;
     int mid=(l+r)>>1;
     int res=-INF;
     if(ql<=mid)res=max(res,big(x<<1,l,mid,ql,qr));
     if(mid<qr)res=max(res,big(x<<1|1,mid+1,r,ql,qr));
     return res;
}
int ask(int x,int l,int r,int ql,int qr)
{
     if(ql<=l&&r<=qr)return seg[x].sum;
     int mid=(l+r)>>1;
     int res=0;
     if(ql<=mid)res+=ask(x<<1,l,mid,ql,qr);
     if(mid<qr)res+=ask(x<<1|1,mid+1,r,ql,qr);
     return res;
}
void dfs1(int now)
{
     son[now]=-1;
     num[now]=1;
     for(auto i:path[now])
     {
          if(!dep[i])
          {
               dep[i]=dep[now]+1;
               p[i]=now;
               dfs1(i);
               num[now]+=num[i];
               if(son[now]==-1||num[i]>num[son[now]])son[now]=i;
          }
     }
}
int cnt;
void dfs2(int now,int t)
{
     top[now]=t;
     cnt++;
     dfn[now]=cnt;
     if(son[now]==-1)return;
     dfs2(son[now],t);
     for(auto i:path[now])
          if(i!=p[now]&&i!=son[now])
               dfs2(i,i);
}
int path_big(int x,int y)
{
     int res=-INF;
     while(top[x]!=top[y])
     {
          if(dep[top[x]]<dep[top[y]])swap(x,y);
          res=max(res,big(1,1,n,dfn[top[x]],dfn[x]));
          x=p[top[x]];
     }
     if(dfn[x]>dfn[y])swap(x,y);
     res=max(res,big(1,1,n,dfn[x],dfn[y]));
     return res;
}
int path_sum(int x,int y)
{
     int res=0;
     while(top[x]!=top[y])
     {
          if(dep[top[x]]<dep[top[y]])swap(x,y);
          res+=ask(1,1,n,dfn[top[x]],dfn[x]);
          x=p[top[x]];
     }
     if(dfn[x]>dfn[y])swap(x,y);
     res+=ask(1,1,n,dfn[x],dfn[y]);
     return res;
}
void solve()
{
     cin>>n;
     FOR(i,0,n-1)
     {
          int a,b;cin>>a>>b;
          path[a].push_back(b);
          path[b].push_back(a);
     }
     dep[1]=1;
     dfs1(1);
     dfs2(1,1);
     FOR(i,1,n+1)
     {
          int now;cin>>now;
          update(1,1,n,dfn[i],now);
     }
     int q;cin>>q;
     while(q--)
     {
          string now;cin>>now;
          if(now=="CHANGE")
          {
               int x,y;cin>>x>>y;
               update(1,1,n,dfn[x],y);
          }
          else if(now=="QMAX")
          {
               int x,y;cin>>x>>y;
               cout<<path_big(x,y)<<endl;
          }
          else
          {
               int x,y;cin>>x>>y;
               cout<<path_sum(x,y)<<endl;
          }
     }
}
signed main()
{
     Yuubari_chan_kawaii
     solve();
}

:::

### [LibreOJ #2125](https://loj.ac/p/2125)

也是裸題 這邊我們看到他需要維護一個子樹的加值
我們只需要對每個節點維護一個值 表示所有其子節點$dfn$的最大值 表為$mx$
那麼對一個點$i$而言$dfn_i$到$mx_i$這個連續的區間裡所有點都是$i$的子節點
我們一樣可以用線段樹來做維護 利用懶人標記的技巧可以讓時間複雜度達到$O(N\log N+Q\log N\log N)$

## 感謝各位 祝大家都能夠在比賽隨手刻出來