總有一天會用到的筆記

本站為減緩筆者下列疑難雜症誕生：記性很差，學過就忘；智商低落，囫圇吞棗。

0%

【題解】TOJ 637. 本田小狼

發表於 更新於 分類於

 題意

給一顆有根樹。多次詢問 \(p\)、\(k\)，求 \(p\) 的子樹往下最多走 \(k\) 步可以到達幾個節點。

觀察

若從 \(u\) 往下走 \(k\) 步可以到達 \(v\)，等價於 \(d[v] \le d[u]+k\)。題目相當於詢問 \(u\) 子樹內有多少子節點深度 \(\le d[u]+k\)。

作法

區間查詢 \(x\) 數量

給你一個序列 \(a\)，多筆查詢 \(\le k\) 的數字有多少。我們可以對值域開一個序列上的資料結構 \(cnt\)，當出現值為 \(x\) 的元素就 \(cnt[x]++\)，查詢時答案就是 \(cnt[1]+...+cnt[k]\)。

進階一點，給你一個序列 \(a\)，多筆區間查詢 \(\le k\) 的數字有多少。只要我們能只把 \(a[l], a[l+1], ..., a[r]\) 放進資料結構，就能用同樣的方式查詢。

如果序列只有一種值，那等於只要 \(r\) 時有多少個減 \(l\) 時有多少個就可以得出答案。推廣到整個序列的很多種值，我們只要每個資料結構的每個位置相減就行：把 \(a[i]\) 放進陣列後，我們紀錄現在的 \(cnt\) 為 \(cnt_i\)，當只要 \(a[l], a[l+1], ..., a[r]\) 放進陣列的結果，就把 \(cnt_r\) 跟 \(cnt_l\) 的每個元素相減得到 \(cnt_p\) 。

我們的 \(cnt\) 以持久化線段樹實作，支援單點修改、查詢版本 \(i\) 下的區間和。

持久化線段樹

因為每次修改只會更動 \(logn\) 個值，我們只要紀錄被更改的節點就好。

對於每次修改我們想像開一顆新的線段樹作為最新的版本，但是子樹若長得完全ㄧ樣就指回去上個版本。

實作要注意：

  • 修改時必須回傳新的節點
  • 若子樹一樣必須指回去上個版本
  • 從外面呼叫修改時，要拿一個陣列儲存新的線段樹的根
  • 可以不用事先 build，全部指到 \(0\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int root[N];
struct Seg{
    int tr[N<<5], lc[N<<5], rc[N<<5], ptr;
    
    int modify (int u, int i, int x, int l=1, int r=n){
        int rt = ++ptr;
        lc[rt] = lc[u], rc[rt] = rc[u], tr[rt] = tr[u];
        if (l == r){
            tr[rt] += x;
        }
        else{
            int m = (l+r)>>1;
            if (i <= m) lc[rt] = modify(lc[u],i,x,l,m);
            if (m < i)  rc[rt] = modify(rc[u],i,x,m+1,r);
            tr[rt] = tr[lc[rt]] + tr[rc[rt]];
        }
        return rt;
    
    }
    int query (int u, int ql, int qr, int l=1, int r=n){
        if (ql<=l && r<=qr){
            return tr[u];
        }
        int m = (l+r)>>1, ans = 0;
        if (ql<=m) ans += query(lc[u],ql,qr,l,m);
        if (m<qr) ans += query(rc[u],ql,qr,m+1,r);
        return ans;
    }
} st;

樹壓平

題目都是查詢子樹，因此只要保證子樹在連續區間內，就能套用上面的方法。

dfs 進去時紀錄 \(tin[u] = ++time\)，出來時紀錄 \(tout[u] = ++time\)。因為一定子樹走完才會出來，因此子樹一定被 \(tin[u]\) 和 \(tout[u]\) 夾住。

有個優化的方式，出來時不佔用另一個 \(time\)，就讓多個 \(tout\) 指在同一個地方，如此序列大小減半且答案不需要除以 \(2\)。

1
2
3
4
5
6
7
8
9
10
int dseq[N], tin[N], tout[N], tim;
void dfs (int u, int fa, int d){
    tin[u] = ++tim;
    dseq[tin[u]] = d;
    for (auto v: G[u]){
        if (v == fa) continue;
        dfs(v,u,d+1);
    }
    tout[u] = tim;
}

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
const int N = 1e6+10;

int n, q;
vector<int> G[N];

int dseq[N], tin[N], tout[N], tim;
void dfs (int u, int fa, int d){
    tin[u] = ++tim;
    dseq[tin[u]] = d;
    for (auto v: G[u]){
        if (v == fa) continue;
        dfs(v,u,d+1);
    }
    tout[u] = tim;
}

int root[N];
struct Seg{
    int tr[N<<5], lc[N<<5], rc[N<<5], ptr;
    int modify (int u, int i, int x, int l=1, int r=n){
        int rt = ++ptr;
        lc[rt] = lc[u], rc[rt] = rc[u], tr[rt] = tr[u];
        if (l == r){
            tr[rt] += x;
        }
        else{
            int m = (l+r)>>1;
            if (i <= m) lc[rt] = modify(lc[u],i,x,l,m);
            if (m < i)  rc[rt] = modify(rc[u],i,x,m+1,r);
            tr[rt] = tr[lc[rt]] + tr[rc[rt]];
        }
        return rt;
    
    }
    int query (int u, int ql, int qr, int l=1, int r=n){
        if (ql<=l && r<=qr){
            return tr[u];
        }
        int m = (l+r)>>1, ans = 0;
        if (ql<=m) ans += query(lc[u],ql,qr,l,m);
        if (m<qr) ans += query(rc[u],ql,qr,m+1,r);
        return ans;
    }
} st;

signed main(){
    minamisan
    cin >> n;
    rep(i,2,n){
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    dfs(1,1,1);
    
    rep(i,1,n){
        root[i] = st.modify(root[i-1],dseq[i],1);
    }
    
    cin >> q;
    rep(i,1,q){
        int p, k;
        cin >> p >> k;
        cout << (st.query(root[tout[p]],1,k+dseq[tin[p]])-st.query(root[tin[p]-1],1,k+dseq[tin[p]])) << '\n';
    }
}