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;
}