これは勉強になりました。
https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_h
問題
N頂点の木を成す無向グラフが与えられる。
各辺には移動時間が設定されている。
このグラフにおいて、M回コンテストが行われる。
各コンテストでは、開始時間・終了時間・開催場所・優勝賞金の情報が与えられる。
コンテストの時間中ずっとその場所に滞在し、かつ他のコンテストに参加しない場合、コンテストに参加・優勝して賞金を得ることができる。
時刻0で任意の頂点から開始し、最適な移動経路を通ったとき、得られる優勝賞金の総和の最大値を答えよ。
解法
仮にグラフが平衡二分木であったとする。
以下の2値を管理し、時系列で更新していくことにしよう。
S(v) := その時点で頂点vに滞在している場合の賞金総和の最大値
T(c) := その時点でコンテストcに参加する場合の賞金総和の最大値
以下の更新タイミングを時系列にソートし、順次更新すればO(MlogN)で済む。
- コンテストcが終了後、親方向に順次祖先の頂点vに対しS(v)を更新する
- コンテストcが始まる前、親方向から順次祖先の頂点vに対しS(v)の値を元にT(c)を更新する
ただ、実際は木は平衡二分木とは限らないので、祖先の頂点数はO(N)になりうるので全体でO(MN)かかりうる。
そこで、グラフを繰り返し重心分解し、分割時の頂点を順次祖先とみなすようにしよう。
そうすると各頂点の祖先の頂点数はO(logN)となり間に合う。
int N,M; int A[101010],B[101010],D[101010]; vector<pair<int,ll>> E[101010]; vector<pair<int,ll>> E2[101010]; int vis[101010]; int NV[101010]; ll st[101010],en[101010],C[101010],X[101010]; ll dp[70707]; ll tobe[70707]; int dfs(int cur,int pre) { NV[cur]=1; FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) NV[cur]+=dfs(e.first,cur); return NV[cur]; } int dfs2(int cur,int pre,int TNV) { int tot=1; int ok=1; FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) { int c = dfs2(e.first,cur,TNV); if(c!=-1) return c; tot += NV[e.first]; if(NV[e.first]*2>TNV) ok=0; } if((TNV-tot)*2>TNV) ok=0; if(ok) return cur; return -1; } int dfs3(int cur,int pre,int base,ll d) { E2[cur].push_back({base,d}); FORR(e,E[cur]) if(e.first!=pre && vis[e.first]==0) dfs3(e.first,cur,base,d+e.second); } void split(int cur) { int TNV = dfs(cur,-1); int center=dfs2(cur,-1,TNV); dfs3(center,-1,center,0); vis[center]=1; FORR(e,E[center]) if(vis[e.first]==0) split(e.first); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N-1) { cin>>x>>y>>r; x--; y--; E[x].push_back({y,r}); E[y].push_back({x,r}); } split(0); vector<vector<ll>> ev; FOR(i,M) { cin>>st[i]>>en[i]>>C[i]>>X[i]; C[i]--; FORR(e,E2[C[i]]) { ev.push_back({(int)st[i]-(int)e.second,1,e.first,i}); ev.push_back({(int)en[i]+(int)e.second,0,e.first,i}); } } sort(ALL(ev)); ll ret=0; FORR(e,ev) { if(e[1]==1) { tobe[e[3]]=max(tobe[e[3]],dp[e[2]]+X[e[3]]); } else { dp[e[2]]=max(dp[e[2]],tobe[e[3]]); ret=max(ret,dp[e[2]]); } } cout<<ret<<endl; }
まとめ
重心分解することで直径の長い木を直径に短い木に変換するテク、ほかにも使えそう。