UVa1218 - Perfect Service

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3659

解題策略DP

dp[u][0]:u是伺服器，則u的子節點可以是也可以不是伺服器

dp[u][1]:u不是伺服器，u的父節點是伺服器,則u的所有子節點都不是伺服器，如果子節點出現伺服器，則u同時連結兩個伺服器，不符合規定

dp[u][2]:u不是伺服器，u的父節點不是伺服器，則u的兒子恰好有一個是伺服器

狀態轉移，v是u的子節點

dp[u][0]=sum{min(dp[v][0],dp[v][1])}+1  =>   u的子節點可以是也可以不是伺服器

dp[u][1]=sum(dp[v][2])   =>  u的所有子節點都不是伺服器

dp[u][2]=min(dp[u][1]-dp[v][2]+dp[v][0])

dp[u][1]=sum(dp[v][2])，帶入上式

dp[u][2]=min(sum(dp[v][2])-dp[v][2]+dp[v][0])   =>  列舉所有v取最小，u的兒子(v)恰好有一個是伺服器

初始化,若u是葉子節點，dp[u][0]=1，dp[u][1]=0,dp[u][2]=INF，INF設為10005