2014-10-17

b327. 學姊日談

1. 內容：
2. 輸入說明：
3. 輸出說明：
4. 範例輸入：
5. 範例輸出：
6. Solution 1
7. Solution 2

內容：

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』
Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

輸入說明：

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

輸出說明：

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行，保證總和可以在 signed 32 bits 內。

範例輸入：

範例輸出：

Solution 1

先將一棵樹壓平，壓平的方式為採用前序走訪。壓樹的另一個思考方式就是換成括弧表示法。(A (B) (C(D)(E))) 類似的情況。壓樹之後，每個節點對應一個左右括弧位置，當我們增加節點 v 權重時，相當於將所有區間的內數字加上 k (子樹的所有節點到根的花費)。

因此我們的問題變成

操作 [l, r]：將區間內的所有數字加上 k
詢問 x：詢問位置 x 元素的值。

下面使用 Binary indexed tree 示範區間調整，單點詢問。

對於 ADD [l, r] k 時，相當於 BIT[l] += k, BIT[r+1] -= k，單點詢問相當於找前綴和 [1, x] 的結果。

每個操作時間複雜度 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
struct Tree {
    vector<int> g[MAXN];
    int root;	
    void init(int n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        root = 0;
    }
    void addEdge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tree;
int bPos[MAXN], ePos[MAXN], inOrder[MAXN<<1], inIdx = 0;
void prepare(int u, int p) {
    bPos[u] = ePos[u] = ++inIdx, inOrder[inIdx] = u;
    for (int i = 0; i < tree.g[u].size(); i++) {
        int v = tree.g[u][i];
        if (v == p)	continue;
        prepare(v, u);
    }
    ePos[u] = ++inIdx, inOrder[inIdx] = u;
}
int bitTree[MAXN<<1];
void modify(int x, int N, int val) {
    while (x <= N) {
        bitTree[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += bitTree[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int n, q, x, y;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        tree.init(n);
        
        int on[MAXN] = {};
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree.addEdge(x, y);
        }
        
        inIdx = 0;
        prepare(tree.root = 0, -1);
        memset(bitTree, 0, sizeof(bitTree));
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d %d", &x, &y);
            modify(bPos[x], inIdx, y);
            modify(ePos[x] + 1, inIdx, -y);
            printf("%d\n", query(bPos[x]));
        }
        puts("");
    }
    return 0;
}

Solution 2

這個解法直接使用樹鏈剖分，樹鏈剖分將子樹節點數量最大的當作重邊，其餘皆為輕邊。將以重邊相連的所有節點，看似一個鏈狀，當作一個 1D Array 看待。

保證每個點爬到 root，只會經過 log n 的輕邊，而中間鏈狀處理，可以使用 segment tree 等之類的樹來壓縮處理時間。

下面為樹鏈剖分的解法，詢問效率 O(log^2 n)，調整 O(log n)。

#include <stdio.h> 
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 32767
int hNext[MAXN], iNode[MAXN], aPos[MAXN];
int used[MAXN], nodesize = 0;
struct Node {
    int p, pPos;
    vector<int> A;
    vector<int> BIT;
    void init() {
        A.clear(), BIT.clear();
        p = -1;
    }
} nodes[262144];
struct Tree {
    vector<int> g[MAXN];
    int root;	
    void init(int n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        root = 0;
    }
    void addEdge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }
} tree;
int prepare(int u, int p) {
    int sz = 1, mx = 0, hedge = -1;
    int v, t;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i], t;
        if (v == p)	continue;
        sz += (t = prepare(v, u));
        if (mx < t)
            mx = t, hedge = v;
    }
    hNext[u] = hedge;
    return sz;
}
void build(int u, int p) {	
    if (used[u] == 0) {
        Node &nd = nodes[++nodesize];
        nd.init();
        for (int i = u; i != -1; i = hNext[i]) {
            used[i] = 1;
            iNode[i] = nodesize, aPos[i] = nd.A.size();
            nd.A.push_back(i);
        }
        nd.BIT.clear(), nd.BIT.resize(nd.A.size() + 10, 0);
        if (p != -1)	nd.p = iNode[p], nd.pPos = aPos[p];
    }
    int v;
    for (int i = 0; i < tree.g[u].size(); i++) {
        v = tree.g[u][i];
        if (v == p)	continue;
        build(v, u);
    }
}
int queryBIT(vector<int> &BIT, int x) {
    int ret = 0;
    while (x)
        ret += BIT[x], x -= x&(-x);
    return ret;
}
void modifyBIT(vector<int> &BIT, int x, int val, int L) {
    while (x <= L)
        BIT[x] += val, x += x&(-x);
}
void search(int u) {
    int sum = 0;
    set< pair<int, int> >::iterator it, jt;
    for (int i = iNode[u], in = aPos[u]; i != -1; in = nodes[i].pPos, i = nodes[i].p)
        sum += queryBIT(nodes[i].BIT, in + 1);
    printf("%d", sum);
    puts("");
}
void modify(int u, int val) {
    Node &nd = nodes[iNode[u]];
    int pos = aPos[u];
    modifyBIT(nd.BIT, pos + 1, val, nd.A.size());
}
int main() {
    int n, q, x, y;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        tree.init(n);
        
        int on[MAXN] = {};
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree.addEdge(x, y);
        }
        
        prepare(tree.root = 0, -1);
        memset(used, 0, sizeof(used));
        nodesize = 0;
        build(tree.root = 0, -1);
        
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d %d", &x, &y);
            modify(x, y);
            search(x);
        }
        puts("");
    }
    return 0;
}

Morris' Blog

b327. 學姊日談

contents

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

Solution 1

Solution 2

contents

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution 1

Solution 2

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：