Codeforces 246 E. Blood Cousins Return
問題
家計図が与えられる。
家計図は、(名前、その人の親)の情報がn個与えられることにより与えられる。
この家計図に対して、次のようなq個のクエリに答えよ。
クエリ: 人v[i]の、ちょうどk代目の子孫のうち、異なる名前の数を答える。
制約条件
n≦10^5
q≦10^5
方針
自分の方針は以下の通り。
まずは家計図をDFSしてeular-tourを作る。
これは、DFSの行きがけと、帰りがけに、vectorにその要素の番号をプッシュした数列である。
各要素がちょうど2度ずつ出現し、なおかつ部分木の全ての要素は、
その部分木の根の二つの間に挟まれる。
深さごとにeular-tourの要素をvectorにして取り出す。
v[i]の人の深さ+kの深さ(=dとする)の部分のうち、
v[i]の子孫となっている部分を見たい。
これは、深さdの列において、eular-tourの順で(v[i]の左側の位置, v[i]の右側の位置)の部分である。
これは2分探索をすればわかる。
列がわかったら、この中のユニークな名前の数を数える。
これは、数列において、[l, r)のユニークな要素の個数を数える問題なので、平方分割して数えればいい。
http://d.hatena.ne.jp/simezi_tan/20111121/1321874269
ここでやったような感じ。
だったんだけど、同じクエリだけメモ化しておけば、あとはなんか愚直にやるだけで通るっぽい。
ソースコード
const int MX = 100010; const int SIZE = 3500; int n, N; int p[MX]; string name[MX]; map<string, int> id; vector<vi> e; int sz; int tour[MX * 2]; int depth[MX]; int leftp[MX], rightp[MX]; vi seq[MX]; vi pos[MX]; int q; int ans[MX]; vector<pair<pi, pi> > qs[MX]; //l / SIZE, r, l, id [depth] void rec(int c, int p, int d){ depth[c] = d; leftp[c] = sz; tour[sz++] = c; rep(i, e[c].size()) if(e[c][i] != p){ rec(e[c][i], c, d + 1); } rightp[c] = sz; tour[sz++] = c; } int main(){ cin >> n; e.resize(n + 1); rep(i, n){ cin >> name[i] >> p[i]; if(p[i] == 0) p[i] = n; else p[i]--; e[p[i]].pb(i); e[i].pb(p[i]); if(!id.count(name[i])) id[name[i]] = N++; } rec(n, n, 0); rep(i, sz){ seq[depth[tour[i]]].pb(id[name[tour[i]]]); pos[depth[tour[i]]].pb(i); } cin >> q; rep(i, q){ int v, k; cin >> v >> k; v--; int L = leftp[v]; int R = rightp[v]; int d = depth[v] + k; if(d >= MX) d = MX - 1; int l = lower_bound(all(pos[d]), L) - pos[d].begin(); int r = upper_bound(all(pos[d]), R) - pos[d].begin(); qs[d].pb(mp(mp(l / SIZE, r), mp(l, i))); } rep(d, MX){ if(qs[d].empty()) continue; sort(all(qs[d])); int curl = 0; int curr = 0; int c = 0; map<int, int> cnt; vi &v = seq[d]; rep(i, qs[d].size()){ int l = qs[d][i].second.first; int r = qs[d][i].first.second; while(r < curr) if(--cnt[v[--curr]] == 0) c--; while(curr < r) if(cnt[v[curr++]]++ == 0) c++; while(curl < l) if(--cnt[v[curl++]] == 0) c--; while(l < curl) if(cnt[v[--curl]]++ == 0) c++; ans[qs[d][i].second.second] = c; } } rep(i, q) cout << ans[i] << endl; return 0; }