yukicoder : No.386 貪欲な領主

★３か４か悩ましいところ。
http://yukicoder.me/problems/no/386

問題

木を成すグラフが与えられる。
各頂点はコストU[i]が与えられる。

また、M個のクエリが与えられる。
各クエリは２頂点A[i],B[i]と値C[i]からなる。
各クエリに対し、A[i]-B[i]間の最短路上にある頂点のコストの総和にC[i]を掛けたものを求め、その総和を求めよ。

解法

木を根付き木と見なし、各頂点vに対しvから根頂点までのコストの総和T[v]を求めておく。
また、LCAを求められるよう前処理しておこう。

各クエリに対しLCM(A[i],B[i])=D[i]とすると、答えに加算する値は(T[A[i]]-T[D[i]])+(T[B[i]]-T[D[i]])+U[D[i]]となるので、C[i]して総和を取ろう。

int N,M;
vector<int> E[200005];
int P[21][200005],D[200005];
int U[202020];
int T[202020];
ll ret;

void dfs(int cur) {
	T[cur]+=U[cur];
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1,T[*it]=T[cur],P[0][*it]=cur, dfs(*it);
}
int getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return cur;
}

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 solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	FOR(i,N) cin>>U[i];
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	cin>>M;
	while(M--) {
		cin>>x>>y>>i;
		int lc=lca(x,y);
		int tot=T[x]-T[lc]+T[y]-T[lc]+U[lc];
		ret += i*tot;
	}
	cout<<ret<<endl;
	
}

まとめ

10000円以下の所持金で過ごす人の横で、この領主は数億円も税金を取っているのね。