P3629 [APIO2010]巡逻（树的直径）

本文主要是介绍P3629 [APIO2010]巡逻（树的直径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

---

易错点：

• l2必须要设置全局变量而不能设置局部变量，这是由于设置局部变量无法兼顾所有情况造成的.
• bfs并设置直径上边权为-1后，如果k=2则不能继续直接使用bfs获得答案，这是bfs的拓展加点性造成的（类比dijkstra）.
• 如果两个变量可以用一个变量导出就用一个变量. 

BFS方法正确性的证明：

• 如果源点在直径上：显然正确.
• 如果源点不在直径上：既然源点不在直径上那么直径一定在源点的某棵子树内。由树和直径的性质可知此时直接取最远点然后再进行一次bfs即可求得直径.

---

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=2e5,INF=0x3f3f3f3f;
struct Edge{int from,to,w,nxt;
}e[MAXN*2];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].w=w;e[edgeCnt].nxt=head[u];head[u]=edgeCnt;
}
int n;
int d[MAXN],pre[MAXN];
int bfs(int p){memset(d,0x3f,sizeof(d));queue<int> q;q.push(p);d[p]=pre[p]=0;while(!q.empty()){int nowNode=q.front();q.pop();for(int i=head[nowNode];i;i=e[i].nxt){int nowV=e[i].to;if(d[nowV]==INF){d[nowV]=d[nowNode]+e[i].w;pre[nowV]=i;q.push(nowV);}}}int ans=1;for(int i=1;i<=n;i++){if(d[i]>d[ans])ans=i;//如果两个变量可以用一个变量导出就用一个变量. }return ans;
}
int p;
int get(){p=bfs(1);p=bfs(p);return d[p];
}
void change(){for(;pre[p];p=e[pre[p]].from){e[pre[p]].w=e[pre[p]^1].w=-1;}
}
bool vis[MAXN];
int f[MAXN],l2;
void dfs(int p){vis[p]=1;for(int i=head[p];i;i=e[i].nxt){int nowV=e[i].to;if(!vis[nowV]){dfs(nowV);l2=max(l2,f[p]+f[nowV]+e[i].w);f[p]=max(f[p],f[nowV]+e[i].w);}}
}
int main(){int k;scanf("%d%d",&n,&k);for(int i=1;i<=n-1;i++){int a,b;scanf("%d%d",&a,&b);addEdge(a,b,1);addEdge(b,a,1);}int l1=get();if(k==1){printf("%d\n",2*(n-1)-l1+1);return 0;}else{change();dfs(1);printf("%d\n",2*n-l1-l2);return 0;}
}

 

这篇关于P3629 [APIO2010]巡逻（树的直径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---