1919 Marbles on a tree
問題概要
木の頂点それぞれに何個かおはじきが置いてある。
一度の操作で、好きなおはじきを一つを、隣り合う頂点のうち好きなものに移動させることができる。
全ての頂点に1つずつおはじきが置かれた状態にするために必要な操作の回数の最小値を求めよ。
n≦10000を満たす。
解法
ある部分木iに対する必要な操作の回数について考える。
部分木の根iに全ての過不足を集めるのにかかる操作の回数をdp2[i]、
部分木におけるおはじきの過不足をdp[i]とすると、
dp2[i]=Σ{abs(dp[j])+dp2[j]|jはiの子}
dp[i]=iのおはじき-1+Σ{dp[j]|jはiの子}
であるので、漸化式が立ちDPできる。
ソースコード
vector<vector<int> > e; int n,m[10000],in[10000],root; int dp[10000],dp2[10000]; void rec(int c){ dp[c]=m[c]-1; dp2[c]=0; fr(i,e[c]){ rec(*i); dp[c]+=dp[*i]; dp2[c]+=dp2[*i]+abs(dp[*i]); } } int main(){ while(scanf("%d",&n),n){ e.clear(); e.resize(n); rep(i,n){ int a,b,c,d; scanf("%d%d%d",&a,&b,&c); a--; m[a]=b; rep(j,c)scanf("%d",&d),e[a].pb(--d),in[d]++; } rep(i,n)if(in[i]==0)root=i; rec(root); printf("%d\n",dp2[root]); } return 0; }