Codeforces #434 Div1 E. Arkady and a Nobody-men

何とか通ってよかった。
http://codeforces.com/contest/860/problem/E

問題

N頂点の根付き木が与えられる。
各頂点のrankとは、根からの距離である。
aとその祖先bに対し、信頼度r(a,b)をbのsubtreeのうち、rankがbより大きくaのrank以下のものとする。
頂点aの微小性(negligibilityのいい役が思いつかなかった)とは、aの祖先の各bに対し、r(a,b)の総和とする。

各頂点の微小性を求めよ。

解法

微小性の別の計算方法を考える。
rankがa以下の頂点bがどの程度aの微小性に寄与するかを考えよう。
bがaの祖先の場合rank(b)、そうでない場合はrank(lca(a,b))+1となる。

aの親頂点をa'とし同じbがどの程度a'の微小性に寄与するかを考えよう。
bのrankがaと同じなら、bはa'よりrankが大きいので寄与は0である。
そうでなければ、aと同様rank(b)またはrank(lca(a,b))+1となる。

つまり、aの微小性を考える際、a未満のrankの頂点の寄与はa'の微小性への寄与と等しい。
よってa'の微小性を求めてあれば、aの微小性を求める際にa'の微小性を加算することでrankがa未満の頂点の処理は完了する。

あとは、aと同じrankの各bについてrank(lca(a,b))+1の総和を求めればよい。
aに対してbを総当たりすると最悪O(N^2)かかるが、同rankの頂点を並べておいて、スライド最小値の要領で隣接する同rankの頂点のLCAを適宜求めていき、累積和でrank(lca(a,b))+1の総和を求めればO(N)で済む。

int N;
int P[20][505050],D[505050];
ll ret[505050];
vector<int> E[505050];

vector<int> ev[505050];

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void dfs(int cur,int dep) {
	D[cur]=dep;
	ev[D[cur]].push_back(cur);
	FORR(e,E[cur]) dfs(e,dep+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	
	int root=-1;
	FOR(i,N) {
		scanf("%d",&P[0][i+1]);
		if(P[0][i+1]==0) root=i+1, P[0][i+1]=root;
		else E[P[0][i+1]].push_back(i+1);
	}
	
	dfs(root,0);
	FOR(i,19) FOR(x,N) P[i+1][x+1]=P[i][P[i][x+1]];
	
	for(i=1;i<=N;i++) if(ev[i].size()) {
		FORR(e,ev[i]) ret[e]=ret[P[0][e]]+D[e];
		FOR(j,2) {
			vector<vector<int>> V;
			ll sum=0;
			FOR(x,ev[i].size()) {
				int e=ev[i][x];
				if(x==0) {
					V.push_back({e,-1,0});
				}
				else {
					while(1) {
						int cand=V.back()[0];
						int lc=lca(cand,e);
						if(V.back()[1]<D[lc]) {
							V.push_back({e,D[lc],x});
							break;
						}
						sum-=1LL*(V[V.size()-1][2]-V[V.size()-2][2])*(V[V.size()-1][1]+1);
						V.pop_back();
					}
					sum+=1LL*(V[V.size()-1][2]-V[V.size()-2][2])*(V[V.size()-1][1]+1);
					ret[e]+=sum;
				}
				
			}
			reverse(ALL(ev[i]));
		}
	}
	
	FOR(i,N) printf("%" PRIu64 "%c", ret[i+1],(i==N-1)?'\n':' ');
	
}

まとめ

本番、TLE覚悟で解法の正当性を確認するためO(N^2)解を出したらキューはつまるわpretest通っちゃうわunratedになるわで参った。