Codeforces #292 Div1 D. Drazil and Morning Exercise

この木DPは珍しかったかも。
http://codeforces.com/contest/516/problem/D

問題

地中に虫の巣がある。
巣は木の形状をしたグラフの形をしており、N個の頂点と距離付の(N-1)本の無向辺で表現される。
次数１の点は地表そば（地上までの距離０）と見なせる。

ある頂点にいる虫は、運動のため(同じ場所を２回通らないようにして)最も長い距離を通って地上に出ようとする。

ここでM個のクエリL[i]が与えられる。
各クエリに対し、連結した頂点群であり、地上に出るまでの距離の最小値と最大値の差がL[i]以下になるような物のうち最大数の頂点群を求め、その頂点数を求めよ。

解法

まず適当な点を根とし、てDFSを２回行い、各頂点iから地上までの最長距離D[i]を求める。

• 1回目で各頂点におけるサブツリー中の葉からの最長距離を求める。
• 2回目で親側を経由した場合の最長距離を伝搬させる。

こうして各点に置ける地上までの最長距離を求めた後、その距離が最小な点を根と見なした木を考える。
この木では、歯に近づくほど地上までの距離が増加していく。
各クエリjにおいてDFSを１回行い、各頂点xにおいてxのサブツリー中でD[x]≦D[y]≦D[x]+L[j]となる頂点y数をカウントし、その最大値をクエリの解として返せばよい。

D[x]≦D[y]≦D[x]+L[j]となるyを直接求めようとするとO(N^2)かかりTLEする。
DFSの際、子の頂点数を親に伝搬させつつ、「yを通ったときにD[y]-Lより小さなD[x]となるxではyをカウントできない」と考えていけば良い。

int N,Q;
vector<pair<int,int> > E[101000];
pair<int,int> P[101000];
ll D[2][101000];
ll L,ma;
vector<pair<ll,int> > S;
int Minu[101000],ret;

ll dfs1(int cur,int pre) {
	int i;
	FOR(i,E[cur].size()) if(E[cur][i].first != pre) D[0][cur] = max(D[0][cur], dfs1(E[cur][i].first,cur)+E[cur][i].second);
	return D[0][cur];
}

void dfs2(int cur,int pre,ll tot) {
	int i;
	vector<pair<ll,int> > V;
	V.emplace_back(tot,cur);
	FOR(i,E[cur].size()) if(E[cur][i].first != pre) V.emplace_back(D[0][E[cur][i].first]+E[cur][i].second,E[cur][i].first);
	sort(V.begin(),V.end());
	reverse(V.begin(),V.end());
	FOR(i,E[cur].size()) if(E[cur][i].first != pre) {
		if(V[0].second==E[cur][i].first) dfs2(E[cur][i].first, cur, V[1].first+E[cur][i].second);
		else dfs2(E[cur][i].first, cur, V[0].first+E[cur][i].second);
	}
	D[1][cur]=V[0].first;
}

int dfs3(int cur,int pre) {
	ll ma=0;
	int tot=1;
	int i;
	
	S.push_back(make_pair(D[1][cur],cur));
	FOR(i,E[cur].size()) if(E[cur][i].first != pre) tot += dfs3(E[cur][i].first,cur);
	S.pop_back();
	tot -= Minu[cur];
	ret=max(ret,tot);
	
	vector<pair<ll,int> >::iterator it=lower_bound(S.begin(),S.end(),make_pair(D[1][cur]-L,0));
	if(it!=S.begin()) {
		it--;
		Minu[it->second]++;
	}
	return tot;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x-1].emplace_back(y-1,r);
		E[y-1].emplace_back(x-1,r);
	}
	dfs1(0,-1);
	dfs2(0,-1,0);
	int piv=0;
	FOR(i,N) if(D[1][piv]>D[1][i]) piv=i;
	cin>>Q;
	while(Q--) {
		cin>>L;
		ret=0;
		ZERO(Minu);
		S.clear();
		dfs3(piv,-1);
		cout<<ret<<endl;
	}
}

まとめ

DFS2回で最遠の葉を求めるところまでは出来たが、その後のDFSが自力では組めなかった。