HackerRank 101 Hack 51 : C. Train Trip

ミス連発したけど全完できました。
https://www.hackerrank.com/contests/101hack51/challenges/train-trip

問題

N頂点の木が与えられる。
３人の初期位置が与えられる。
それぞれ辺をたどり根頂点に移動することを考える。

各辺は各自任意のタイミングで移動でき、同時に移動する人数1,2,3によって移動コストがA,B,Cと変わる。
全員が根頂点に到達する最小コストを求めよ。

解法

全員が根頂点に直行するのがベストとは限らない点に注意。
A,Bが大きくCが小さい場合、3人中一人が余分に移動してでも3人合流して一緒に移動した方が良いケースもある。
一方、1人が余分に移動して2人合流して得するケースは考慮しなくてよい(わざわざAコストをかけて迎えに行って、2人でBコストをかけて戻るなら、最初からAコストをかけて遠い側の人が根に近づけばよい)。

問題はどこで合流するかだが、面倒なので下記は全頂点でそれぞれ合流したケースを総当たりしている。
1人または2人での移動を繰り返し、合流地点vまで移動し、vから根まで3人で移動するケースのコストを順次求めた。
合流地点まで1人と2人どちらで移動するかだが、3人のうち合流地点までの共通経路の長い2人を求め、その２人がバラバラと一緒どっちに移動した方が良いかを考えればよい。

int T;
int N;
ll A,B,C;
int V[3];

vector<int> E[200005];
int P[21][200005],D[200005];

void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}
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>>T;
	while(T--) {
		cin>>N;
		cin>>A>>B>>C;
		cin>>V[0]>>V[1]>>V[2];
		V[0]--,V[1]--,V[2]--;
		FOR(i,N) E[i].clear(),D[i]=0;
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		dfs(0);
		FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
		
		ll di[3][3]={};
		FOR(x,3) FOR(y,3) di[x][y]=D[V[x]]+D[V[y]]-2*D[lca(V[x],V[y])];
		
		ll mi=1LL<<60;
		FOR(i,N) {
			ll L[3]={};
			FOR(j,3) L[j]=D[V[j]]+D[i]-2*D[lca(V[j],i)];
			ll same=max({L[0]+L[1]-di[0][1],L[1]+L[2]-di[1][2],L[2]+L[0]-di[2][0]})/2;
			
			ll ret=min(A*(L[0]+L[1]+L[2]),A*(L[0]+L[1]+L[2]-2*same)+B*same);
			
			mi=min(mi,ret+C*D[i]);
		}
		cout<<mi<<endl;
		
	}
}

まとめ

余分に移動してでも合流するルートを思いつくまで時間がかかった。