まぁまぁ良かった回。
https://codeforces.com/contest/2006/problem/B
問題
根付き木が与えられる。
また、この木はDFS訪問順に番号が振られている。
各辺eには、非負整数値コストT[e]があり、その和はWだとする。
以下のクエリが行われるので、そのつど、点i-(i+1)間のパスのコストを最大値の総和を求めよ。
各パスのコストを求めるとき、未定の辺のコストは個別に最適に割り振ってよい。
- コストが未知の1つの辺を1つ確定させる。
解法
各辺は全パスにおいていずれも2回だけカウントされる。
逆に1つ辺のコストが確定すると、それにより影響を受けるパスは高々2個である。
まず、各辺のコストが定まったときに影響を受ける2つのパスを明らかにしよう。
また、各パスの最大値を求めるとき、未確定の辺が1個でもあれば、未割当のコストをそこに全振りしてよい。
割り当て済みのコストをF、未確定の辺が1個でもあるパスをn個とすると、解はF+(W-F)*n。
辺の内容を確定させながら、Fとnの更新差分を求めて行こう。
int T; int N; ll W; int P[202020],D[202020]; vector<int> E[202020]; ll V[202020]; int NE[202020]; vector<int> ev[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>W; FOR(i,N) { E[i].clear(); ev[i].clear(); V[i]--; NE[i]=0; } for(i=1;i<N;i++) { cin>>P[i]; P[i]--; D[i]=D[P[i]]+1; E[P[i]].push_back(i); } FOR(i,N) { x=i; y=(x+1)%N; while(D[x]>D[y]) { ev[x].push_back(i); x=P[x]; NE[i]++; } while(D[x]<D[y]) { ev[y].push_back(i); y=P[y]; NE[i]++; } while(x!=y) { ev[y].push_back(i); y=P[y]; ev[x].push_back(i); x=P[x]; NE[i]+=2; } } ll unfix=W*N; ll fix=0; int num=N; FOR(i,N-1) { ll X,Y; cin>>X>>Y; X--; FORR(v,ev[X]) { fix+=Y; NE[v]--; if(NE[v]==0) num--; } W-=Y; ll sum=fix+W*num; cout<<sum<<" "; } cout<<endl; } }
まとめ
Bにしてはちょっと面倒だと思ったら、やっぱり1250ptだったか。