CODE FESTIVAL 2015 決勝 : I - 風船ツリー

これは幸い本番自力で通せた。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_i

問題

N個のヒモ付風船が根付き木を成すように結ばれている。
各風船の紐の長さをL[i]とする。

風船の高さは、親頂点の高さに自身の紐の長さを加えたものとする。
(根である1番の風船は、L[1]が高さとなる)

ここでQ個のクエリが与えられる。
各クエリは高さH[j]からなる。
根付き木中最も高い位置にある風船がH[j]となるよう、いくつかのヒモを切りたい。
達成可能なら、ヒモを切る数の最小数を求めよ。

解法

以下風船をグラフの頂点として考える。

各頂点の高さをX[i]とする。
各頂点iについて、「i番の頂点を残し、かつX[i]より高い位置にある頂点をすべて消せるようなヒモ切り数」を求めよう。

まず、消したい頂点がある場合、その頂点の紐を直接切るよりも、その親を切った方が良い。
どちらを必要なコストは同じなので、それなら多くの頂点を消せるほうが良いためである。
ただし、消したくない頂点まで消しては困るので、消したくない頂点の1つ子の頂点のヒモを切ると良い。

i番の頂点を残す場合、1→i番に至る経路はすべて残さなければならない。
他、1→i番に至る経路にある頂点の子頂点のうち、1→i番の経路上には無いもので、かつそのSubtreeにX[i]より高い頂点を持つものをすべて消したい。
i自身の子頂点はすべてX[i]以上の高さの頂点なので、これらはすべて消さなければならない。

よって残るは1→parent(i)における上記子頂点数を数え上げよう。
木の左側から順にDFSしているとする。
頂点Vの子頂点A,B,C...を順にDFSするとき、AのSubtreeの最高の高さ、BのSubtreeの最高の高さ…を順にBITをインクリメントしていこう。
C及びそのSubTreeを探索するときには、BITにA,Bの最高の高さが入っているので、A,BのSubTreeがX[i]を超えるものを含むかどうか容易に計算できる。

同様にもう一度DFSを行う。
ただし今度は逆順に...,C,B,AとBITを処理しながらDFSする。
そうすると今後はA及びそのSubTreeを探索するとき、B,CのSubTreeにX[i]を超えるものを含むかどうか容易に計算できる。

各頂点を残すのに必要な最小ヒモ切り数がわかれば、あとはクエリに答えていくだけ。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

int N,Q;
vector<int> E[101010];
int L[101010],P[101010],D[101010],ma[101010],num[101010];

vector<int> PR;
map<int,int> ret,rev;

void dfs(int cur,int order) {
	int i,tar;
	num[cur] += bt(1000000)-bt(D[cur]);
	
	FOR(i,E[cur].size()) {
		if(order==0) tar=E[cur][i];
		else tar=E[cur][E[cur].size()-1-i];
		dfs(tar,order);
		bt.add(ma[tar],1);
	}
	
	FOR(i,E[cur].size()) bt.add(ma[E[cur][i]],-1);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i], D[i]=L[i];
	
	FOR(i,N-1) {
		cin>>P[i+1];
		P[i+1]--;
		E[P[i+1]].push_back(i+1);
		D[i+1]=L[i+1]+D[P[i+1]];
	}
	
	PR.push_back(0);
	FOR(i,N) PR.push_back(D[i]);
	sort(ALL(PR));
	PR.erase(unique(ALL(PR)),PR.end());
	FOR(i,PR.size()) rev[PR[i]]=i;
	
	for(i=N-1;i>=0;i--) {
		D[i]=lower_bound(ALL(PR),D[i])-PR.begin();
		ma[i]=max(ma[i],D[i]);
		ma[P[i]]=max(ma[P[i]],ma[i]);
		num[i]+=E[i].size();
	}
	dfs(0,0);
	assert(bt(1000000)==0);
	dfs(0,1);
	
	FOR(i,N) {
		if(ret.count(D[i])==0) ret[D[i]]=1000000;
		ret[D[i]]=min(ret[D[i]],num[i]);
	}
	
	cin>>Q;
	while(Q--) {
		cin>>x;
		if(rev.count(x)==0) cout<<-1<<endl;
		else cout<<ret[rev[x]]<<endl;
	}
	
}

まとめ

これは本番うまく思いつけて良かった。