正題

題目鏈接:https://jzoj.net/senior/#contest/show/3005/1

---

題目大意

一棵樹，一個信息開始給一個人，每次得到信息的人可以選擇相鄰節點中的一個傳遞，求最短多久可以傳到所有人。

---

解題思路

我們先考慮如何求一根的答案，$fa{r}_i$表示第$i$個點的傳遞玩子樹所需要的最短時間，顯然對于子節點的$far$排個序依次傳遞就好了。

之后考慮換根，對于一個節點我們要求出從這個父節點不需要傳遞該節點時的最短時間$u{p}_i$，這個值在父節點操作時可以求出。

對于$dp$到的節點$x$，我們將子節點的$far$和$u{p}_x$丟進去排序，然后用一個前綴$max$和一個后綴$max$求出來所有子節點的$up$還可以順便求出該點答案。

時間復雜度$:O(n\log n)$

---

$code$

注意這里并沒有使用$up$數組，而是覆蓋掉$far$數組來使用

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=2e5+10; struct node{int to,next; }a[N*2]; int tot,ls[N],pre[N],aft[N]; int n,far[N],ans[N],answer; vector<int> q[N]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } bool cmp(int x,int y) {return far[x]>far[y];} void dfs(int x,int fa){int maxx=0,maxy=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa) continue;dfs(y,x);q[x].push_back(y);}sort(q[x].begin(),q[x].end(),cmp);for(int i=0;i<q[x].size();i++)far[x]=max(far[q[x][i]]+i+1,far[x]);return; } int dp(int x,int fa){if(fa)q[x].push_back(x);sort(q[x].begin(),q[x].end(),cmp);for(int i=1;i<=q[x].size();i++)pre[i]=max(pre[i-1],far[q[x][i-1]]+i);for(int i=q[x].size();i>=1;i--)aft[i]=max(aft[i+1],far[q[x][i-1]]+i);ans[x]=max(ans[x],pre[q[x].size()]);answer=min(answer,ans[x]);for(int i=0;i<q[x].size();i++){int y=q[x][i],z;far[y]=max(pre[i],aft[i+2]-1); }for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa) continue;dp(y,x);} } int main() {freopen("news.in","r",stdin);freopen("news.out","w",stdout);scanf("%d",&n);for(int i=2;i<=n;i++){int x;scanf("%d",&x);addl(i,x);addl(x,i);}answer=2147483647;dfs(1,1);dp(1,0);printf("%d\n",answer+1);for(int i=1;i<=n;i++)if(ans[i]==answer)printf("%d ",i);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的jzoj3501-消息传递【换根法,树形dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。