Tree(1):树分治与动态点分治 2019-05-10

  1. 点分治

点分治是解决树上问题的常用算法,具体思想为把一个大问题分成两个子问题然后分别解决,复杂度为

\[T(n)=T(\frac{n}{2})+O(\text{merge})\]

对于树上问题同样可以采取分治的策略,定义重心为一个树中去掉重心使得剩下的子树大小中最大的最小的那个点。显然重心的最大子树不会大于当前树大小的\(\frac{1}{2}\),可以用反证法证明。同样的可以得到一个类似分治复杂度的算法,复杂度为

\[T(n)=T(\frac{n}{2})+O(\text{merge})\]

常见套路

  • 查询树上的最大最小值
  • 查询树上满足条件的路径条数

例题1 BZOJ2599

  • 查询一棵树中的经过边最少的路径使得路径为\(P\),输出最小的边。

考虑分治处理子树,合并的过程可以用std::set维护一个std::pair<int,int>存子树到自己的距离和边数。每次用set.lower_bound合并信息。

同时可以每个子树,统计出在子树中的答案,由于当前要考虑的只是过顶点的答案。采用容斥的思想,加上自己的答案,减去子树内的答案。

const int maxn = 2e5 + 10;
int n, p, cent, heavy, nodeCnt;
int size[maxn]; bool Del[maxn];
template<typename T> inline void chkmax(T &x, T y) { x < y ? x = y : 0; }
template<typename T> inline void chkmin(T &x, T y) { x > y ? x = y : 0; }
#define pb push_back
#define mp make_pair

vector<pair<int,int> >e[maxn];

void gr(int x, int from) {
  size[x] = 1; int mx = 0;
  for (int pt = 0; pt < e[x].size(); ++pt) {
    pair<int,int>Tr = e[x][pt];
    int to = Tr.first; 
    if (to == from || Del[to]) continue;
    gr(to, x); size[x] += size[to];
    chkmax(mx, size[to]);
  }
  chkmax(mx, nodeCnt - size[x]);
  if (mx <= heavy) { heavy = mx; cent = x; }
}

int ans = (int)(1e9);

pair<int,int> stk[maxn]; int top;
void dfs(int x, int from, int Dis, int Cnt) {
  if (Cnt > ans || Dis > p) return;
  stk[++top] = mp(Dis, Cnt);
  for (int pt = 0; pt < e[x].size(); ++pt) {
    pair<int,int>Tr = e[x][pt];
    int to = Tr.first; 
    if (to == from || Del[to]) continue;
    dfs(to, x, Dis + Tr.second, Cnt + 1);
  } 
}

typedef set<pair<int, int> >::iterator sit;

set<pair<int, int> >st;
void Solve(int x, int Size) {
  heavy = nodeCnt = Size; cent = 0;
  gr(x, x);
  Del[cent] = 1;
  
  st.insert(mp(0ll, 0));
  int Root = cent;
  for (int pt = 0; pt < e[Root].size(); ++pt) {
    pair<int,int>Tr = e[Root][pt];
    int to = Tr.first;
    if (!Del[to]) {
      top = 0;
      dfs(to, Root, Tr.second, 1);
      for (int i = 1; i <= top; ++i) {
        assert(p >= stk[i].first);
        sit It = st.lower_bound(mp(p - stk[i].first, 0));
        if (It != st.end() && It->first + stk[i].first == p)
          ans = min(ans, It->second + stk[i].second);
      }
      for (int i = 1; i <= top; ++i) st.insert(stk[i]);
    } 
  }
  st.clear();
  for (int pt = 0; pt < e[Root].size(); ++pt) {
    pair<int,int>Tr = e[Root][pt];
    int to = Tr.first;
    if (!Del[to]) {
      Solve(to, size[to]);
    }
  }
}

int main() {
  n = read(); p = read();
  for (int i = 1; i < n; ++i) {
    int x = read() + 1, y = read() + 1, w = read();
    e[x].pb(mp(y, w)); e[y].pb(mp(x, w));
  }
  Solve(1, n);
  if (ans == (int)(1e9)) cout << "-1";
  else printf("%lld", ans);
  return 0;
}

 

以上是点分治的两种合并方法对于不同的问题可能存在一种更好写

边分治

原理同点分治,只不过点分治选取的重心,而边分治选取的是中心边。中心边定义为删去这条边后使得两边的子树最大的最小的边。

对于菊花图或类菊花图这一类的图,边分治复杂度会退化,所以需要重建树。重建树的操作类似建立虚树时的虚点,把一个有两个以上子节点的树的子树中加入虚点。

例题2 BZOJ2870

  • 定义树上路径(u,v)的价值为点的个数乘路径上点权的最小值,求最小代价路径。

考虑边分治,过当前这条边的答案,和点分治差不多,只是把点分治处理点换成处理边。注意要转成二叉树保证复杂度

bool del[maxn];
int n, cnt = 1, heavy, cent, nodeCnt, od_n;
ll ans;
int sz[maxn], val[maxn], head[maxn];
vector<int>G[maxn];
class edge {
public:
    int to, next, from;
}e[maxn << 2]; 
IL void add_single_edge(int x, int y) { e[++cnt].from = x; e[cnt].to = y; e[cnt].next = head[x]; head[x] = cnt; }
IL void add_edge(int x, int y) {  
    add_single_edge(x, y); add_single_edge(y, x);  
}
void rebuild_tree(int u, int fa) {
    int f = 0;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (v == fa) continue;
        if (!f) {
            add_edge(u, v);
        //  f = u;
        } else {
            int k = ++n; val[k] = INF;
            add_edge(f, k);
            add_edge(k, v);
            f = k;
        }
        rebuild_tree(v, u);
    }
}
void findct(int u, int fa) {
    sz[u] = 1; 
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (del[i >> 1] || v == fa) continue;
        findct(v, u);
        sz[u] += sz[v];
        int cur_size = max(sz[v], nodeCnt - sz[v]);
        if (cur_size < heavy) {
            heavy = cur_size;
            cent = i;
        }
    }
}

class Info {
public:
    int dep, mn;
    Info() {}
    Info(int x, int y) : dep(x), mn(y) {} 
    IL bool operator < (const Info &rhs) const { 
        return mn > rhs.mn;
    } 
}stk1[maxn], stk2[maxn];
int top1, top2;

IL void get_info(Info *stk, int x, int fa, int dep, int Mn, int &top) {
    stk[++top] = Info(dep, Mn == INF ? 0 : Mn); 
    for (int i = head[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (del[i >> 1] || v == fa) continue;
        get_info(stk, v, x, dep + (v <= od_n), min(Mn, val[v]), top);
    }
}

void solve(int edge_num) {
    int lp = e[edge_num].from; int rp = e[edge_num].to;
    del[edge_num >> 1] = 1;
    top1 = top2 = 0;
    get_info(stk1, lp, lp, lp <= od_n, lp <= od_n ? val[lp] : INF, top1); 
    get_info(stk2, rp, rp, rp <= od_n, rp <= od_n ? val[rp] : INF, top2); 
    
    sort(stk1 + 1, stk1 + 1 + top1); sort(stk2 + 1, stk2 + 1 + top2);
    for (int i = 1, j = 1, mx = 0; i <= top1; ++i) {
        while (j <= top2 && stk2[j].mn >= stk1[i].mn) mx = max(mx, stk2[j].dep), j++;
        if (j != 1) ans = max(ans, 1ll * (stk1[i].dep + mx) * stk1[i].mn);
    }
    for (int i = 1, j = 1, mx = 0; j <= top2; ++j) {
        while (i <= top1 && stk2[j].mn <= stk1[i].mn) mx = max(mx, stk1[i].dep), i++;
        if (i != 1) ans = max(ans, 1ll * (stk2[j].dep + mx) * stk2[j].mn);
    }
    if (sz[lp] > sz[rp]) swap(lp, rp);
    int tot = nodeCnt, tmp = sz[lp]; 
    nodeCnt = heavy = sz[lp]; cent = 0;
    findct(lp, lp); 
    if (cent) solve(cent);
    nodeCnt = heavy = tot - tmp; cent = 0;
    findct(rp, rp); 
    if (cent) solve(cent);
}

IL void DC() {
    nodeCnt = heavy = n; cent = 0;
    findct(1, 0);
    solve(cent);
}
int main() {
    od_n = n = read();
    for (int i = 1; i <= n; ++i) val[i] = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G[u].pb(v); G[v].pb(u);
    }
    rebuild_tree(1, 0);
    DC();
    printf("%lld\n", ans);
    return 0;
}

动态点分治

动态点分治是在解决点分治的基础上带修改等问题的技巧。

定义把点分治当前点和划分出的重心连边连出的树为点分树,由于点分治层数不会超过\(\log\)级别,所以树高不会超过\(\log\),对于每次修改只会在点分树上影响父节点,那么可以在点分树上暴力修改,复杂度为\(\log\)级别。

常见套路

  • 查询以某个点开始的路径信息
  • 查询整棵树的路径信息
  • 查询路径信息的同时,支持给树填加叶子节点
  • 所有的动态点分治都有修改操作

例题3 BZOJ1095

  • 多次修改树上点的颜色(黑白),多次询问树上最远黑点对之间距离

在每个点开两个堆,第一个堆插入这个重心管辖的一坨树所有黑点到分治树上这个点父亲的距离,第二个堆插入所有点分治树上孩子的堆顶,这样我们就可以对于每个分治重心,找到分属两棵子树的深度最大的两个黑点,即这个点堆的最大和次大值。

为了统计答案,我们还要再开一个堆来维护答案。

为了删除堆中的元素,需要再开一个堆,如果要删除就把东西丢到另外一个堆里面,如果两个堆堆顶相同就删除。

#include <bits/stdc++.h>
using namespace std;
#define IL inline
IL int read() {
    char ch = getchar(); int u = 0, f = 1;
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
    return u * f;
}
const int maxn = 5e5 + 10;
template<typename T> inline void chkmax(T &x, T y) { x < y ? x = y : 0; }
template<typename T> inline void chkmin(T &x, T y) { x > y ? x = y : 0; }

template<typename T>
class Heap {
private:
    priority_queue<T>ord, era;
public:
    Heap() {}
    IL void push (T x) { ord.push(x); }
    IL void erase(T x) { era.push(x); }
    IL void pop () { while (era.size() && ord.top() == era.top()) ord.pop(), era.pop(); ord.pop(); }
    IL T    top () { 
        while (era.size() && ord.top() == era.top()) ord.pop(), era.pop(); 
        return ord.size() ? ord.top() : T(0); 
    }
    IL int size () { return ord.size() - era.size(); }
    IL T    sec () { if (size() < 2) return T(0); T x = top(); pop(); T y = top(); push(x); return y; }
};

Heap<int> A, B[maxn], C[maxn];
vector<int>e[maxn];
bool del[maxn];
int size[maxn], par[maxn];
int cent, heavy, nodeCnt;

void gr(int x, int from) {
    size[x] = 1; int mx = 0;
    for (int to : e[x]) {
        if (to != from && !del[to]) 
            gr(to, x),
            size[x] += size[to],
            chkmax(mx, size[to]);
    }
    chkmax(mx, nodeCnt - size[x]);
    if (mx < heavy) {
        heavy = mx;
        cent = x;
    }
}

void Solve (int x, int from) {
    par[x] = from; del[x] = 1;
    for (int to : e[x]) {
        if (!del[to]) {
            heavy = nodeCnt = size[to];
            gr(to, to);
            Solve(cent, x);
        }
    }
}

IL void DDC (int n) {
    heavy = nodeCnt = n;
    gr(1, 0);
    Solve(cent, 0);
}

int dep[maxn], dfn[maxn], dfscnt, pos[maxn];

class StTable {
private:
    int a[maxn][20], pw[maxn];
public:
    IL void BuildSt(int *b, int n) {
        pw[0] = -1; for(int i = 1; i <= n; i++) pw[i] = pw[i >> 1] + 1;
        memset(a, 0x3f, sizeof a);
        for (int i = 1; i <= n; ++i) a[i][0] = b[i];
        for (int i = 1; i < 20; ++i) {
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                a[j][i] = min(a[j][i - 1], a[j + (1 << (i - 1))][i - 1]);
        }
    }
    IL int Query(int x, int y) {
        if (x > y) swap(x, y);
        int dist = pw[y - x + 1];
        int res = min(a[x][dist], a[y - (1 << dist) + 1][dist]);
        return res;
    }
}stb;

IL void prep(int x, int fa) {
    dfn[++dfscnt] = x; dep[x] = dep[fa] + (fa ? 1 : 0); pos[x] = dfscnt;
    for (int to : e[x]) {
        if (to == fa) continue;
        prep(to, x);
        dfn[++dfscnt] = x;
    }
} 

IL int dist(int x, int y) {
    return dep[x] + dep[y] - 2 * stb.Query(pos[x], pos[y]);
}

bool black[maxn];
int blackCnt;

IL void Turn_Off(int cur, int who) {
    if (cur == who) {
        B[cur].push(0);
        if (B[cur].size() == 2) A.push(B[cur].top());
    }
    if (!par[cur]) return;
    int f = par[cur], D = dist(f, who), tmp = C[cur].top();
    C[cur].push(D);
    if (D > tmp) {
        int mx = B[f].top() + B[f].sec(), Sz = B[f].size();
        if (tmp) B[f].erase(tmp);
        B[f].push(D);
        int now = B[f].top() + B[f].sec();
        if (now > mx) {
            if (Sz >= 2) A.erase(mx);
            if (B[f].size() >= 2) A.push(now);
        }
    }
    Turn_Off(f, who);
}

IL void Turn_On(int cur, int who) {
    if (cur == who) {
        if (B[cur].size() == 2) A.erase(B[cur].top());
        B[cur].erase(0);
    }
    if (!par[cur]) return;
    int f = par[cur], D = dist(f, who), tmp = C[cur].top();
    C[cur].erase(D);
    if (D == tmp) {
        int mx = B[f].top() + B[f].sec(), Sz = B[f].size();
        B[f].erase(D);
        if (C[cur].top()) B[f].push(C[cur].top());
        int now = B[f].top() + B[f].sec();
        if (now < mx) {
            if (Sz >= 2) A.erase(mx);
            if (B[f].size() >= 2) A.push(now);
        }
    }
    Turn_On(f, who);
}

int main() {
    int n = read();
    for (int i = 1; i < n; ++i) {
        int v = read(), u = read();
        e[v].push_back(u); e[u].push_back(v);
    }
    prep(1, 0);
    static int temp[maxn];
    for (int i = 1; i <= dfscnt; ++i) temp[i] = dep[dfn[i]];
    stb.BuildSt(temp, dfscnt);
    
    DDC(n);
        
    /*cerr << "==== [ new edge ] ====\n";
    for (int i = 1; i <= n; ++i)
        cerr << i << " " << par[i] << endl;*/
    
    for (int i = 1; i <= n; ++i)
        Turn_Off(i, i), black[i] = 1;
    blackCnt = n; 
    
    int Q = read(); static char ope[2];
    while (Q--) {
        int _w = scanf("%s", ope);
        if (ope[0] == 'C') {
            int x = read(); 
            if (black[x]) blackCnt--, Turn_On(x, x);
            else blackCnt++, Turn_Off(x, x);
            black[x] ^= 1;
        } 
        else {
            if (blackCnt == 1) puts("0");
            else if (blackCnt == 0) puts("-1");
            else {
                printf("%d\n", A.top());
            }     
        }
    }
    return 0;
}

例题4 BZOJ3730

  • 多次修改一个点的点权,多次查询到一个点距离不大于\(k\)的点的点权

考虑不带修,只需要暴力分治的时候dfs一下,如果带修,则可以用权值线段树维护树上距离为d点的点到自己的点权和。

一颗线段树中,对点分树中以u为根的子树中的节点v,我们以他距u的距离为下标,点权为值插入线段树

另一颗里,对点分治中以u为根的子树中的节点v,我们以他距u的父亲节点距离为下标,点权为值插入线段树

第一颗树的目的是为了统计答案,第二步是为了减去算重的贡献。

一个例子 转自CSDN

当算到\(7\)的时候,由于\(2\)的第二颗线段树下表为1的点是0(到7号的距离为1),但是在上轮中已经被计算过了\((3\geq 1)\),所以这个时候要减去它的贡献。

#include <bits/stdc++.h>
using namespace std;
#define IL inline
#define re register 

IL void chkmax(int x, int y) { x = (x < y) ? y : x; }

namespace Faster {
      const int L = 1 << 15;
      char buffer[L], *S, *T;
  IL char Getchar(){
    if(S == T){
      T = (S = buffer) + fread(buffer, 1, L, stdin);
      if (S == T) return EOF;
    }
    return *S++;
  }
  template <class T> inline void read(T &in){
    char c;
    for(c = Getchar();c > '9' || c < '0';c = Getchar());
    for(in = 0;c >= '0' && c <= '9';c = Getchar()) in = (in << 1) + (in << 3) + c - 48;
  }   
}

const int maxn = 2e5 + 10;
const int maxn_Log = 6e6 + 10;

class st {
public:
  int a[int(4e5 + 10)][18], pw[int(4e5 + 10)];
  IL void build(int *b, int n) {
    pw[0] = -1;
    for (int i = 1; i <= n; ++i) pw[i] = pw[i >> 1] + 1;
    memset(a, 0x3f, sizeof a);
    for (int i = 1; i <= n; ++i) a[i][0] = b[i];
    for (int i = 1; i < 18; ++i) 
      for (int j = 1; j <= n; ++j)
        a[j][i] = min(a[j][i - 1], a[j + (1 << i - 1)][i - 1]);
  }
  IL int q(int l, int r) {
    if (l > r) swap(l, r); 
    re int g = pw[r - l + 1];
    return min(a[l][g], a[r - (1 << g) + 1][g]);
  }
}stb;

int n, m, lastans;
class Edge {
public:
  int to, next; 
}e[maxn];
int head[maxn], cnt;
IL void insert(int x, int y) { e[++cnt].to = y; e[cnt].next = head[x]; head[x] = cnt; }
int val[maxn], sz[maxn], par[maxn], dep[maxn], dfn[int(4e5 + 10)], pos[maxn], dfscnt; 
bool del[maxn];
int cent, heavy, nodecnt;
void dfs(int x, int fa) {
  dfn[++dfscnt] = x; pos[x] = dfscnt;
  for (int i = head[x]; i; i = e[i].next) {
    int v = e[i].to;
    if (v == fa) continue;
    dep[v] = dep[x] + 1;
    dfn[++dfscnt] = x;
    dfs(v, x);
  }
}
IL int dist(int x, int y) {
  return dep[x] + dep[y] - 2 * stb.q(pos[x], pos[y]);
}
void gr(int x, int from) {
  int mx = 0; sz[x] = 1;
  for (int i = head[x]; i; i = e[i].next) {
    int v = e[i].to;
    if (v == from || del[v]) continue;
    gr(v, x); sz[x] += sz[v];
    mx = max(mx, sz[v]);    
  }
  mx = max(mx, nodecnt - sz[x]);
  if (mx < heavy) { heavy = mx; cent = x; }
}
void solve(int x, int from) {
  par[x] = from; del[x] = 1;
  for (int i = head[x]; i; i = e[i].next) {
    int v = e[i].to;
    if (!del[v]) {
      cent = 0; heavy = nodecnt = sz[v];
      gr(v, x);
      solve(cent, x);
    }
  }
}
IL void prep() {
  cent = 0; heavy = nodecnt = n;
  gr(1, 0); 
  solve(cent, 0);
}

int rt[maxn], ls[maxn_Log], rs[maxn_Log], sum[maxn_Log], segcnt;
IL void mdi(int &p, int x, int y, int pos, int add) {
  if (!p) p = ++segcnt; sum[p] += add;
  if (x == y) return;
  re int mid = (x + y) >> 1;
  if (pos <= mid) mdi(ls[p], x, mid, pos, add);
  else mdi(rs[p], mid + 1, y, pos, add);
}
IL int ask(int p, int x, int y, int pos) {
  if (!p) return 0;
  if (pos >= y) return sum[p];
  re int mid = (x + y) >> 1;
  if (pos > mid) return sum[ls[p]] + ask(rs[p], mid + 1, y, pos);
  else return ask(ls[p], x, mid, pos);
} 

IL int tree_query(int x, int y) {
  int ans = ask(rt[x], 0, n - 1, y);
  for (int v = x; par[v]; v = par[v]) {
    int d = dist(par[v], x);
    if (d > y) continue;
    ans += ask(rt[par[v]], 0, n - 1, y - d);
    ans -= ask(rt[v + n],  0, n - 1, y - d);
  }
  return ans;
}

IL void tree_add(int x, int y) {
  mdi(rt[x], 0, n - 1, 0, y);
  for (int v = x; par[v]; v = par[v]) {
    int d = dist(par[v], x);
    mdi(rt[par[v]], 0, n - 1, d, y);
    mdi(rt[v + n],  0, n - 1, d, y);
  }
}

IL int query(int x, int k) {
  return tree_query(x, k);
}
IL void change(int x, int k) {
  tree_add(x, k - val[x]); 
  val[x] = k;
}

int main() {
  using namespace Faster;
  read(n), read(m);
  for (int i = 1; i <= n; ++i) read(val[i]);
  for (int i = 1; i <  n; ++i) {
    int u, v;
    read(u), read(v);
    insert(u, v); insert(v, u);
  }
  
  //dfs init
  dfs(1, 0);
  static int tmp[maxn];
  for (int i = 1; i <= dfscnt; ++i) tmp[i] = dep[dfn[i]];
  stb.build(tmp, dfscnt);
  
  //cerr << dfscnt << endl;
  //divide init
  prep();
  
  for (int i = 1; i <= n; ++i) 
    tree_add(i, val[i]);
  //cerr << segcnt << endl;
  for (int i = 1; i <= m; ++i) {
    bool op; read(op);
    int x, k;
    read(x); x ^= lastans; read(k); k ^= lastans;
    if (!op) printf("%d\n", lastans = query(x, k));
    else change(x, k);
  }
  
  return 0;
}