。。我现在这个状态真是 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:

Posted by xiaodao
Category: Codeforces