Codeforces Global Round 1 : F. Nearest Leaf

本番ここまでが速く解けたのでよい順位だった。
https://codeforces.com/contest/1110/problem/F

問題

重み付き木が与えられる。
なお、その頂点はDFS行き掛け順に番号が振られている。
以下のクエリに順次答えよ。

頂点番号V,L,Rが与えられる。頂点Vから見て、[L..R]の区間中の葉までの最短距離を求めよ。

解法

木の各頂点を探索しつつ、訪問時にその頂点をVとするクエリを処理しよう。
幸い、元の頂点番号がEulerTour順になっている。
よって、訪問のため現在の頂点を移動すると、頂点番号の区間に対し、そこまでの距離が同じ分増加ないし減少するので、区間加算可能で区間の最小値を求められるSegTreeを更新していけばよい。

int N,Q;
int P[505050],W[505050];
vector<pair<int,int>> E[505050];
ll D[505050];

vector<int> cand;
int L[505050],R[505050];
int QL[505050],QR[505050];
vector<int> QS[505050];
ll ret[505050];

static ll const def=1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<ll,1<<20> st;

void dfs(int cur, ll dep) {
	D[cur]=dep;
	L[cur]=cand.size();
	FORR(e,E[cur]) dfs(e.first,dep+e.second);
	if(E[cur].empty()) {
		cand.push_back(cur);
	}
	R[cur]=cand.size();
}

void dfs2(int cur) {
	
	FORR(q,QS[cur]) {
		int CL=lower_bound(ALL(cand),QL[q])-cand.begin();
		int CR=lower_bound(ALL(cand),QR[q])-cand.begin();
		ret[q]=st.getval(CL,CR);
	}
	
	FORR(e,E[cur]) {
		st.update(0,cand.size(),e.second);
		st.update(L[e.first],R[e.first],-2*e.second);
		dfs2(e.first);
		st.update(0,cand.size(),-e.second);
		st.update(L[e.first],R[e.first],+2*e.second);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(i,N-1) {
		scanf("%d%d",&P[i+2],&W[i+2]);
		E[P[i+2]].push_back({i+2,W[i+2]});
	}
	dfs(1,0);
	FOR(i,Q) {
		scanf("%d%d%d",&x,&QL[i],&QR[i]);
		QR[i]++;
		QS[x].push_back(i);
	}
	FOR(i,cand.size()) st.update(i,i+1,D[cand[i]]);
	dfs2(1);
	FOR(i,Q) cout<<ret[i]<<endl;
	
}

まとめ

実装は重いけど、考え方は難しくない。