P2018 消息傳遞
?
題目描述
巴蜀國的社會等級森嚴，除了國王之外，每個人均有且只有一個直接上級，當然國王沒有上級。如果A是B的上級，B是C的上級，那么A就是C的上級。絕對不會出現這樣的關系：A是B的上級，B也是A的上級。
最開始的時刻是0，你要做的就是用1單位的時間把一個消息告訴某一個人，讓他們自行散布消息。在任意一個時間單位中，任何一個已經接到消息的人，都可以把消息告訴他的一個直接上級或者直接下屬。
現在，你想知道：
1.到底需要多長時間，消息才能傳遍整個巴蜀國的所有人？
2.要使消息在傳遞過程中消耗的時間最短，可供選擇的人有那些？
?
?
樹形DP，加入了記憶化，設$dp[u][fa]$表示以$u$為兒子，父親為$fa$的傳遞的最大時間，
狀態轉移方程為$dp[u][fa]=max(dp[u][fa],it[i]+cnt-i+1)$
$it[i]$表示他的子樹的大小，$cnt$表示他子樹的個數；
貪心的走，應該先走最大的子樹，所以走到第$i$小的子樹的時間為$it[i]+cnt-i+1$，即他子樹的大小+傳遞到他的時間+1（向下傳遞）
?
#include<cstdio> #include<iostream> #include<cstdlib> #include<vector> #include<algorithm>#define inf 0x7fffffffusing namespace std;int n,dp[1005][1005],ans; vector<int>G[1005];int dfs(int u,int fa){if(dp[u][fa]) return dp[u][fa];int cnt=0,it[1005],si=G[u].size();for(int i=0;i<si;i++){int v=G[u][i];if(v==fa) continue;it[++cnt]=dfs(v,u);}dp[u][fa]=1;sort(it+1,it+1+cnt);for(int i=1;i<=cnt;i++)dp[u][fa]=max(dp[u][fa],it[i]+cnt-i+1);return dp[u][fa]; }int main() {scanf("%d",&n);for(int u,i=2;i<=n;i++){scanf("%d",&u);G[u].push_back(i);G[i].push_back(u);}ans=inf;for(int i=1;i<=n;i++) ans=min(ans,dfs(i,0));printf("%d\n",ans);for(int i=1;i<=n;i++) if(dp[i][0]==ans) printf("%d ",i);return 0; }
?
