【題目描述】： 一個樹由n個點，n-1條邊組成，結點編號為1…n。樹上任意兩個點之間路徑唯一。定義一個點到一條路徑的距離為該點到路徑上最近的一個點需要經過的邊的數量。現在想知道怎樣選兩個點確定一條路徑，使得距離這個路徑最遠的點盡量近。要求你輸出距離路徑最遠的點距離路徑的距離。【輸入描述】： 第一行一個整數n。其中1≤n≤1000接下來n-1行，每行兩個整數u和v，表示結點u和結點v之間有條邊。【輸出描述】： 一行一個整數，為題目要求的答案。【樣例輸入】： 8 1 2 2 3 1 4 4 5 1 6 6 7 7 8 【樣例輸出】： 2 【樣例說明】： 可以選擇3到7作為一條鏈，那么此時距離這條鏈最遠的點是5,距離為2。可以發現不存在其他的一條鏈，使得最遠點的距離更短。【時間限制、數據范圍及描述】： 時間：1s 空間：256M對于10%的數據，保證n=99998，且樹退化成一條鏈。對于另外30%的數據，保證n=100。對于另外30%的數據，保證n=99999，且答案小于等于5。對于剩余的30%的數據，保證n=100000。本題可以先找樹的直徑,然后從樹的直徑上的每一個點進行dfs,之后統計答案即可.Code: #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<ctime> using namespace std; const int N=100005; int n,head[N],dep[N],fa[N],cnt,ans; bool vis[N]; struct Node{int u,v,nxt; }edge[N*2]; void add(int u,int v){++cnt;edge[cnt].u=u;edge[cnt].v=v;edge[cnt].nxt=head[u];head[u]=cnt; } int bfs(int s){queue<int> q;int depth=s;q.push(s);dep[s]=1;fa[s]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(!dep[v]){dep[v]=dep[u]+1;fa[v]=u;q.push(v);depth=dep[depth]<dep[v]?v:depth;}}}return depth; } int dfs(int u){int s=0;vis[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(!vis[v]){s=max(dfs(v),s);}}return s+1; } int main(){int u,v,re;scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);add(u,v);add(v,u);}re=bfs(1);memset(dep,0,sizeof(dep));memset(fa,0,sizeof(fa));re=bfs(re);for(int i=re;i;i=fa[i]){vis[i]=1;}for(int i=re;i;i=fa[i]){for(int j=head[i];j;j=edge[j].nxt){int v1=edge[j].v;if(!vis[v1]){ans=max(ans,dfs(v1));}}}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11577776.html

總結

以上是生活随笔為你收集整理的UOJ #590. 天天和树的全部內容，希望文章能夠幫你解決所遇到的問題。

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