天天看點
傳回

[SPOJ QTREE] Query on a tree （樹鍊剖分）

連結

SPOJ QTREE

題意

給出一個樹，邊帶權，然後給出若幹個詢問，詢問分QUERY a b和CHANGE i ti兩種，前者查詢節點a、b之間經過不重複路徑的最大邊權，後者改變第i邊權值為ti，對每個QUERY操作輸出相應結果。

題解

樹鍊剖分的裸題。

沈陽網賽上吃了虧，補一下比較進階的資料結構，其實樹鍊剖分并沒想的那麼複雜（對深搜做法而言）。

大緻介紹一下樹鍊剖分，和記錄它的整個過程如下：

樹鍊剖分是用來解決樹區間問題的，這裡的樹區間指的是兩節點之間的不重複路徑經過的每條邊權組成的區間，通過樹鍊剖分可将這些邊映射線上段樹上，用以維護。

對樹中的任意節點i，需要記錄以下資訊：

fa[i]、sz[i]、dep[i]、next[i]、idx[i]、top[i]

fa[i]為i節點的父節點

sz[i]為以i節點為根的子樹的規模

dep[i]為i節點深度，根節點為1，向下深度遞增

next[i]為i節點的子節點中sz最大的節點（多個取其一），即沿着重鍊的下一個節點

idx[i]為以i節點為下端點的邊線上段樹中的位置

top[i]為i節點所在“重鍊”的頭節點

在第一次dfs中可處理出每個點的fa、sz、dep和next：

void dfs1(int u, int f, int d)
{
    fa[u] = f;
    dep[u] = d;
    sz[u] = ;
    next[u] = ;
    for(int i = , v; i < son[u].size(); i++)
    if((v = son[u][i]) != f) {
        dfs1(v, u, d + );
        sz[u] += sz[v];
        if(sz[next[u]] < sz[v])
            next[u] = v;
    }
}

對于一個節點u，它和next[u]的連邊我們記為重邊，和它其它子的連邊為輕邊，接下來的第二次dfs中，将重邊串成一條重鍊，具體表現為鍊上的所有節點都有相同的top。

從根向下遞歸處理，top[1] = 1，對u節點，向其next[u]傳遞top[u]作為top，其它子節點v以v本身作為top，向下遞歸即可。在整個過程中要對每個節點設定idx，注意對每個節點先對其next[u]進行遞歸、再遞歸其它節點，因為我們需要一條重鍊上的idx是連續的，對應線段樹上連續的一段：

int top[maxn], w[maxn], idx[maxn], cnt;
void dfs2(int u, int tp)
{
    top[u] = tp;
    idx[u] = ++cnt;
    if(!next[u]) return ;
    dfs2(next[u], tp);
    for(int i = , v; i < son[u].size(); i++)
    if((v = son[u][i]) != fa[u] && v != next[u]) {
        dfs2(v, v);
    }
}

這樣樹鍊就剖分完成，我們對w[idx[i]]建立線段樹即可維護。

樹鍊剖分的作用在于加速兩個節點間區間的查詢，如果兩個節點a、b位于同一條重鍊，那麼顯然可以query(idx[next[a]], idx[b], 1, n, 1)，如果a、b位于不同重鍊，就讓二者向同一重鍊去靠攏，由于每次都是一條重鍊一條輕邊這樣的跨度，是以二者很快就到了同一重鍊上。

見網上說對任意節點a、b，二者靠攏經過的重鍊和輕邊數均為logn級的，這樣結合線段樹的每次查詢就是lognlogn，st表就是logn了，但是無法更改。

int qtree(int u, int v, int n)
{
    int topu = top[u], topv = top[v], ans = ;
    while(topu != topv)
    {
        // printf("while()\n");
        if(dep[topu] < dep[topv]) { swap(topu, topv); swap(u, v); }
        ans = max(query(idx[topu], idx[u], , n, ), ans);
        u = fa[topu];
        topu = top[u];
    }
    if(u == v) return ans;
    if(dep[u] > dep[v]) swap(u, v);
    ans = max(ans, query(idx[next[u]], idx[v], , n, ));
    return ans;
}

代碼 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define maxn (10010)
struct edge
{
    int a, b, c;
} e[maxn];
vector<int> son[maxn];
int fa[maxn], dep[maxn], sz[maxn], next[maxn];
void dfs1(int u, int f, int d)
{
    fa[u] = f;
    dep[u] = d;
    sz[u] = ;
    next[u] = ;
    for(int i = , v; i < son[u].size(); i++)
    if((v = son[u][i]) != f) {
        dfs1(v, u, d + );
        sz[u] += sz[v];
        if(sz[next[u]] < sz[v])
            next[u] = v;
    }
}
int top[maxn], w[maxn], idx[maxn], cnt;
void dfs2(int u, int tp)
{
    top[u] = tp;
    idx[u] = ++cnt;
    if(!next[u]) return ;
    dfs2(next[u], tp);
    for(int i = , v; i < son[u].size(); i++)
    if((v = son[u][i]) != fa[u] && v != next[u]) {
        dfs2(v, v);
    }
}
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
int seg[maxn << ];
void build(int l, int r, int rt)
{
    if(l == r) { seg[rt] = w[l]; return; }
    int m = (l + r) >> ;
    build(lson), build(rson);
    seg[rt] = max(seg[rt<<], seg[rt<<|]);
}
void update(int x, int val, int l, int r, int rt)
{
    if(l == r) { seg[rt] = val; return; }
    int m = (l + r) >> ;
    if(x <= m) update(x, val, lson);
    else update(x, val, rson);
    seg[rt] = max(seg[rt<<], seg[rt<<|]);
}
int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R) return seg[rt];
    int m = (l + r) >> , ret = -;
    if(L <= m) ret = max(ret, query(L, R, lson));
    if(R > m) ret = max(ret, query(L, R, rson));
    return ret;
}
int qtree(int u, int v, int n)
{
    int topu = top[u], topv = top[v], ans = ;
    while(topu != topv)
    {
        // printf("while()\n");
        if(dep[topu] < dep[topv]) { swap(topu, topv); swap(u, v); }
        ans = max(query(idx[topu], idx[u], , n, ), ans);
        u = fa[topu];
        topu = top[u];
    }
    if(u == v) return ans;
    if(dep[u] > dep[v]) swap(u, v);
    ans = max(ans, query(idx[next[u]], idx[v], , n, ));
    return ans;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int N;
        cin >> N;
        cnt = ;
        for(int i = ; i <= N; i++) son[i].clear();
        for(int i = ; i <= N-; i++)
        {
            scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
            son[e[i].a].push_back(e[i].b);
            son[e[i].b].push_back(e[i].a);
        }
        dfs1(, , );
        dfs2(, );
        for(int i = ; i <= N-; i++)
        {
            if(dep[e[i].a] < dep[e[i].b]) swap(e[i].a, e[i].b);
            w[idx[e[i].a]] = e[i].c;
        }
        build(, N, );
        char op[];
        int a, b;
        while(scanf("%s", op) && op[] != 'D')
        {
            scanf("%d%d", &a, &b);
            if(op[] == 'Q')
                printf("%d\n", qtree(a, b, N));
            else
                update(idx[e[a].a], b, , N, );
        }
        if(t) putchar('\n');
    }
    return ;
}
ACM 資料結構 樹鍊剖分
上一篇: SPOJ QTREE - Query on a tree（樹鍊剖分）
下一篇: SPOJ QTREE-Query on a tree

繼續閱讀