Codeforces Round #151

。。我現在這個狀態真是 SB 到家了啊。。這要是在現場賽就是怒賣隊友了。。。
(。。。還好 DIV 2.。。要不然 p 點又掉一地。。。

Problem E. Blood Cousins Return

Brief description:

給定一顆有根樹、每個結點有一個名字,詢問某個結點往下 k 層有多少不相同的名字。

Analysis:

。。下面兩個演算法都是在線的。。很容易推廣到名字可修改的情況。。(。。修改樹的結構的話還能做么?。

。考慮詢問結點必然處在同一個層的一個區間。。
。因此先 dfs 序。。然後對於某個詢問。。可以二分定位到區間。。
這樣對於每一層就是靜態的。。詢問某個區間有多少不相同的元素。的問題。。數據結構維護即可。。

。。。我猜 watashi 大概就是這麼做的。。(給 Haskell × 4 跪爛!。。

。。我現場生的方法是倍增祖先亂搞。。大概是要反過來再維護出一個 「倍增孩子 列表的東西。。
。因為這樣是一對多。。所以就可能導致中間 dfs() 下去的時候會同時處在好多個狀態。。結果我就 TLE 了。。。

最壞情況是完全二叉樹。。每次詢問最底層的葉子。。則每次的複雜度都是 O(n) 的。。。。

。。賽後看了一下 rng_58 的代碼。。發現它二分定位完區間以後是暴力的。。。。。。
。。。再仔細看了一下好像記錄了一下每次詢問的答案。。遇到相同詢問就不再做了。。
。。然後我把這個也加上。。就過了。。= =(常數大了點。。仔細想一下的話其實這一步很科學。。因為複雜度是 O(n) 的詢問不會超過 O(log(n)) 個。。。

http://codeforces.com/contest/246/submission/2623278

/* .................................................................................................................................. */

const int N = 100009, L = 19;

typedef bitset<N> mask;

char buf[25]; VI adj[N], son[N][L]; MSI H; MPIII M;
int p[N][L], id[N], m, n; mask res;

#define v son[u][lv][i]
void dfs(int u, int k){ // 回答詢問。。。
    if (!k) res.set(id[u]);
    else{
        int lv = low_idx(k) - 1, d = low_bit(k);
        REP(i, SZ(son[u][lv])) dfs(v, k-d);

    }
}
#undef v
#define v adj[u][i]
void gao(int u = 0){ // 倍增祖先。。預處理。。
    REP(i, SZ(adj[u])){
        p[v][0] = u, son[u][0].PB(v); FOR(lv, 1, L){
            p[v][lv] = p[p[v][lv-1]][lv-1];
            if (!p[v][lv]) break;
            son[p[v][lv]][lv].PB(v);
        }
        gao(v);
    }
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    string s; REP_1_C(i, RD(n)){
        RS(buf), s = buf; if (!CTN(H, s)) H[s] = m++;
        id[i] = H[s]; int p; RD(p);
        adj[p].PB(i);
    }

    gao();

    Rush{
        int u, k; RD(u, k); if (!M[MP(u, k)]){
            res.reset(), dfs(u, k);
            M[MP(u, k)] = res.count();
        }
        OT(M[MP(u, k)]);
    }
}

External link: