如何用本机电脑做网站服务器,询价网站哪个好,wordpress注册界面修改密码,英文网站建站模板正题
题目链接:https://jzoj.net/senior/#contest/show/3005/1 题目大意
一棵树#xff0c;一个信息开始给一个人#xff0c;每次得到信息的人可以选择相邻节点中的一个传递#xff0c;求最短多久可以传到所有人。 解题思路
我们先考虑如何求一根的答案#xff0c;farif…正题
题目链接:https://jzoj.net/senior/#contest/show/3005/1 题目大意
一棵树一个信息开始给一个人每次得到信息的人可以选择相邻节点中的一个传递求最短多久可以传到所有人。 解题思路
我们先考虑如何求一根的答案farifar_ifari表示第iii个点的传递玩子树所需要的最短时间显然对于子节点的farfarfar排个序依次传递就好了。
之后考虑换根对于一个节点我们要求出从这个父节点不需要传递该节点时的最短时间upiup_iupi这个值在父节点操作时可以求出。
对于dpdpdp到的节点xxx我们将子节点的farfarfar和upxup_xupx丢进去排序然后用一个前缀maxmaxmax和一个后缀maxmaxmax求出来所有子节点的upupup还可以顺便求出该点答案。
时间复杂度:O(nlogn):O(n\log n):O(nlogn) codecodecode
注意这里并没有使用upupup数组而是覆盖掉farfarfar数组来使用
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N2e510;
struct node{int to,next;
}a[N*2];
int tot,ls[N],pre[N],aft[N];
int n,far[N],ans[N],answer;
vectorint q[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
bool cmp(int x,int y)
{return far[x]far[y];}
void dfs(int x,int fa){int maxx0,maxy0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;dfs(y,x);q[x].push_back(y);}sort(q[x].begin(),q[x].end(),cmp);for(int i0;iq[x].size();i)far[x]max(far[q[x][i]]i1,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 i1;iq[x].size();i)pre[i]max(pre[i-1],far[q[x][i-1]]i);for(int iq[x].size();i1;i--)aft[i]max(aft[i1],far[q[x][i-1]]i);ans[x]max(ans[x],pre[q[x].size()]);answermin(answer,ans[x]);for(int i0;iq[x].size();i){int yq[x][i],z;far[y]max(pre[i],aft[i2]-1); }for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;dp(y,x);}
}
int main()
{freopen(news.in,r,stdin);freopen(news.out,w,stdout);scanf(%d,n);for(int i2;in;i){int x;scanf(%d,x);addl(i,x);addl(x,i);}answer2147483647;dfs(1,1);dp(1,0);printf(%d\n,answer1);for(int i1;in;i)if(ans[i]answer)printf(%d ,i);return 0;
}
