SDOI2013 直径（树的直径必经边）

- 日理万妓 2021-11-23 23:12 301阅读 0赞

### SDOI2013 直径 ###

[题目传送][Link 1]

sol:

先求出任一直径同时把直径拎出来，树的非直径部分全部挂在直径上（如下）。

![a][]

对于直径上的每一个点i，如果存在它到非直径上点的最大距离\\(g\[i\]\\)等于它到直径两端点中较短的那一段\\(d\[i\]\\)，

则说明这一段也可以成为直径中的一部分。

而我们需要得到所有直径的交，画图可以发现假设两端（以中点为界）都存在上述的点，最逼近的两点间的边即为所求！

![b][a]

具体可以看代码实现。

code:

#include<bits/stdc++.h> #define IL inline #define RG register #define DB double #define LL long long using namespace std; IL int gi() { RG int x=0,p=1; RG char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') p=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar(); return x*p; } const int N=2e5+3; LL mx,len,d[N],s[N],g[N]; int n,l,r,S,T,cnt,tot,ans,f[N],fa[N],vis[N],head[N]; struct EDGE{int next,to,v;}e[N<<1]; IL void make(int x,int y,int z) { e[++tot]=(EDGE){head[x],y,z},head[x]=tot; e[++tot]=(EDGE){head[y],x,z},head[y]=tot; } void dfs(int x,int fx) { RG int i,y; for(i=head[x];i;i=e[i].next) if((y=e[i].to)!=fx) d[y]=d[x]+e[i].v,fa[y]=x,dfs(y,x); } void dfs2(int x,int fx,int RT) { RG int i,y; if(d[x]>g[RT]) g[RT]=d[x]; for(i=head[x];i;i=e[i].next) if((y=e[i].to)!=fx&&!vis[y]) d[y]=d[x]+e[i].v,dfs2(y,x,RT); } int main() { RG int i,j,x,y,z; for(i=1,n=gi();i<n;++i) x=gi(),y=gi(),z=gi(),make(x,y,z); for(i=1,dfs(1,0);i<=n;++i) if(d[i]>mx) mx=d[i],S=i; mx=d[S]=0,fa[S]=0,dfs(S,0); for(i=1;i<=n;++i) if(d[i]>mx) mx=d[i],T=i; printf("%lld\n",len=mx); for(i=T;i;i=fa[i]) vis[i]=1,f[++cnt]=i,s[i]=d[i]; for(i=2;i<cnt;++i) d[f[i]]=0,dfs2(f[i],0,f[i]); for(i=1;len-s[f[i]]<=s[f[i]];++i) if(len-s[f[i]]==g[f[i]]) l=i; for(j=cnt;len-s[f[j]]>=s[f[j]];--j) if(s[f[j]]==g[f[j]]) r=j; printf("%d\n",ans=r-l); return 0; } //树的直径和直径必经边

转载于:https://www.cnblogs.com/Bhllx/p/11247456.html

[Link 1]: https://www.luogu.org/problem/P3304
[a]: