結構苦労した。
https://csacademy.com/contest/round-19/#task/road-trips
問題
根付き木が与えられる。
各辺の距離はC[i]である。
M人の子供が根からいずれかの葉に向け移動していく。
各子供jには値V[j]が設定されている。
複数の子供がある辺を通過した場合、(通過した子供のV[j]の最小値)×C[i]がスコアとして加算される。
子供の移動先の葉を最適に設定した場合、スコアの総和を求めよ。
解法
M人の子供がS個の葉頂点に移動するとする。
その場合、V[j]の上位(S-1)人がバラバラの葉頂点に移動し、残り(M-S+1)人がまとまって上位陣とは別の頂点に移動するとよい。
後者の移動経路については、結局(Vの最小値)×C[i]がスコアに加算される。
よって、到達する葉頂点数Sを決めると、考えるべき子供も上位(S-1)人+最下位1人だけ考えればよい。
以下Sを1~Mまで総当たりし、それぞれのスコアの最大値を求めよう。
その際、S人のうちV[j]の小さい順にどの頂点を割り振るか考えていこう。
以下の通りbitDPで解く。
dp(S,mask) := 到達葉頂点数がSであり、S人中V[j]の低いbitcount(mask)人の到達先がmaskであるときのスコアの総和の最大値
今i番目の葉頂点の到達者がいない状態で、新規にi番の頂点の到達者が現れた場合のスコアの更新を考える。
すなわち、dp(S,mask xor (2^i))の値からdp(S,mask)を求めることを考える。
これは、下からbitcount(mask)番目のV[j]の人の行先をi番の葉頂点とすることになる。
よって、途中までの経路はよりV[j]の低い人と一緒に移動する可能性がある。
これを具体的に考えよう。
(mask xor (2^i))のbitmaskに含まれる頂点kそれぞれに対しLCA(i,k)を求め、そのうち最も根から遠い頂点をrとする。
根からrまではよりV[j]の低い人と一緒に移動するので、スコアは増加しない。
r→i番の葉頂点までの距離とV[j]の積の分だけスコアが増加する。
上記処理は愚直に組むとO(M^3*2^M*logN)かかる。
葉頂点は最大M個しかないので、LCAは先にM^2通り求めておくことで、logNを前処理で完了されることができる。
また、iとmaskに対するrの値を前処理しておくとループが1個へる。
両者わせるとO(N+M^2*2^M)で済むようになる。
int N,M; int V[101010]; vector<pair<int,int>> E[101010]; int P[21][101010]; ll D[101010]; ll dist[101010]; vector<int> L,C; 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 pre,ll di,int d) { D[cur]=d; dist[cur]=di; P[0][cur]=pre; FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,di+e.second,d+1); } ll dp[1<<18]; int LCA[20][20]; ll lowest[18][1<<18]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) cin>>V[i]; FOR(i,N-1) { cin>>x>>y>>r; x--,y--; E[x].push_back({y,r}); E[y].push_back({x,r}); } dfs(0,0,0,0); FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]]; FOR(i,N) if(i && E[i].size()==1) L.push_back(i); FOR(y,L.size()) FOR(x,L.size()) LCA[x][y] = lca(L[x],L[y]); FOR(i,1<<L.size()) { FOR(x,L.size()) if(i & (1<<x)) { FOR(y,L.size()) if(x!=y && (i & (1<<y))) lowest[x][i]=max(lowest[x][i],dist[LCA[x][y]]); } } sort(V,V+M); ll ret=0; for(x=1;x<=L.size();x++) { ll V2[20]={}; FOR(i,x) { if(i==0) V2[i]=V[i]; else V2[i]=V[i+(M-x)]; } for(int mask=1;mask<1<<L.size();mask++) { int id=__builtin_popcount(mask)-1; if(id>=x) continue; dp[mask]=-1LL<<60; FOR(i,L.size()) if(mask & (1<<i)) { dp[mask]=max(dp[mask], dp[mask ^ (1<<i)] + (dist[L[i]]-lowest[i][mask])*V2[id]); } ret = max(ret, dp[mask]); } } cout<<ret<<endl; }
まとめ
本番LCA使うところに頭が至らなかった…。