题解 P3304 【[SDOI2013]直径】
Zekrom
2019-05-11 15:37:04
直径必经边
说说主要思路：
首先必经边一定在一条直径上，枚举每一条点（记录前驱），dfs求出该点到非直径上的最长路（树的最长路一遍dfs即可，不用多此一举dijk），如果最长路到直径两端点的距离相同，我们意识到，这条最长路也是直径的一个选择，对于直径的起点和终点，如果都有这样一个断点，两个断点在直径上的距离就为必经边长度
注意：
枚举每一个点dfs求最长路时，在dfs过程中求出最长路的值，避免d数组的重新赋值和循环求出最长路，否则时间复杂度将上升到O（n^2）~~，第一次没注意就这样T了~~
上代码 ：
```cpp
#include<iostream>
#include<cstdio>
#define N 200010
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
int n,pos[N][2],head[N],route[N],num,tot,ans,s,e;
long long ls[N],re[N],d[N],dis[N] ,len,sum;
bool vis[N],v[N];
struct Edge{
int v,next,val;
}edge[N*2];
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();};while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
inline void add(int x,int y,int z){edge[++tot].v=y;edge[tot].next=head[x];edge[tot].val=z;head[x]=tot;}
int bfs(int s){
queue<int>q;q.push(s);memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)d[i]=0;memset(pos,0,sizeof(pos));long long maxn=0;
int maxi;
while(q.size()){
int u=q.front();q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v,z=edge[i].val;
if(vis[v])continue;
d[v]=d[u]+z;
q.push(v);
pos[v][0]=u,pos[v][1]=z;
if(d[v]>maxn)maxn=d[v],maxi=v;
}
}
len=maxn;
return maxi; //被机房称为毒瘤bfs写法求直径（他们都dfs6行orz）
}
void dfs(int s,int fa,int x){
if(!head[s])return ;
for(int i=head[s];i;i=edge[i].next){
int to=edge[i].v,z=edge[i].val;
if(to==fa||v[to])continue;
d[to]=d[s]+z;
dis[x]=max(dis[x],d[to]); //dfs过程中求出dis
dfs(to,s,x);
}
}
int main(){
n=read();
for(int i=1;i<=n-1;i++){int x=read(),y=read(),z=read();add(x,y,z);add(y,x,z);}
s=bfs(1);
e=bfs(s);
int t=e;
route[++num]=e;
v[e]=1;
while(t!=s){//标记路径
re[pos[t][0]]=re[t]+pos[t][1]; //在标记路径时求出直径上点到终点e距离，到起点s距离为直径长len-re[x]
t=pos[t][0];
route[++num]=t;
v[t]=1;
}
for(int i=1;i<=num;i++){
int x=route[i];
d[x]=0;
dfs(x,0,x); //求出dis最长路
}
int tr=1;
for(tr=1;tr<=num;tr++){
int x=route[tr];
if(dis[x]==len-re[x])break; //如果到s距离为最长路,断点1set
}
int tl=num;
for(tl=num;tl>=1;tl--){
int x=route[tl];
if(dis[x]==re[x])break;//同理断点2
}
ans=abs(tr-tl);//这就是必经边数
printf("%lld\n",len);
printf("%d",ans);
return 0;
}
```