题目描述：

点这里

 

题目大意：

就是在一个树上找其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

 

题解：

首先，第一问很好求，两边dfs就行了，第一次从任一点找距它最远的点，再从这个点找距它的最远点，后两个点就是树的直径的两个端点，证明就不赘述了，有兴趣可以自己证一证玩一玩。

那第二问怎么办呢？假设我们有这样一个图（如下）

 

如图所示，中间那根直的就是树的直径之一，旁边标红的也是树的直径。（图画的不好，感性理解）

我们要知道，树的直径是必定会有交叉的，可以画个图自己看一下。

所以就会有一个想法：首先找出一条直径的起点，向终点推，如果碰到交叉，就看这个交叉是否是直径，如果是，就把第一个直径收缩，再继续找。再从终点向起点收缩一遍。

最后就是代码实现了，收缩的过程是真滴玄学。

代码如下：

  1. #include<iostream>
  2. #include<queue>
  3. #include<cmath>
  4. #include<cstdio>
  5. #include<vector>
  6. #include<cstring>
  7. #include<cstdlib>
  8. #include<algorithm>
  9. #define ll long long 
  10. #define rint register int
  11. #define M 200005
  12. using namespace std;
  13. inline int read()
  14. {
  15.     int s=0,f=1;char ch=getchar();
  16.     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  17.     while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
  18.     return s*f;
  19. }
  20. inline ll max(ll a,ll b){return a>b?a:b;}
  21. ll dis[M],maxx,s,t;
  22. ll n,m,cnt,head[M],vis[M];
  23. ll dep[M],father[M],l,r,ans,son[M];
  24. struct edge
  25. {
  26.     int to,nex,v;       
  27. }e[M<<1];
  28. inline void add(int u,int v,int w)
  29. {
  30.     e[++cnt].to=v;
  31.     e[cnt].v=w;
  32.     e[cnt].nex=head[u];
  33.     head[u]=cnt;
  34. }
  35. void dfs(int u,int fa)
  36. {
  37.     for(rint i=head[u];i;i=e[i].nex)
  38.     {
  39.         int v=e[i].to;if(v==fa) continue;father[v]=u;
  40.         dis[v]=dis[u]+e[i].v;dfs(v,u);
  41.     }
  42. }
  43. void find(int u,int fa)
  44. {
  45.     dep[u]=0;ll maxn=0;
  46.     for(rint i=head[u];i;i=e[i].nex)
  47.     {
  48.         int v=e[i].to;if(v==father[u] || vis[v]==1) continue;
  49.         find(v,u);maxn=max(maxn,dep[v]+e[i].v);
  50.     }
  51.     dep[u]=maxn;
  52. }
  53. int main()
  54. {
  55.     n=read();
  56.     for(rint i=1;i<=n-1;++i)
  57.     {
  58.         int x=read(),y=read(),z=read();
  59.         add(x,y,z),add(y,x,z);
  60.     }
  61.     dfs(1,0);
  62.     for(rint i=1;i<=n;++i)
  63.     {
  64.         if(dis[i]>maxx) maxx=dis[i],s=i;
  65.         dis[i]=0;
  66.     }
  67.     dfs(s,0);maxx=0;
  68.     for(rint i=1;i<=n;++i)
  69.     {
  70.         if(dis[i]>maxx) maxx=dis[i],t=i;
  71.     }
  72.     printf("%lld\n",maxx);
  73.     int l=t,r=s,now=t;
  74.     while(now!=s)
  75.     {
  76.         vis[now]=1;
  77.         son[father[now]]=now;
  78.         now=father[now];
  79.     }
  80.     now=t;
  81.     while(now!=s)
  82.     {
  83.         dep[now]=0;
  84.         find(now,0);
  85.         if(dep[now]==maxx-dis[now]) l=now;
  86.         now=father[now];
  87.     }
  88.     now=s;
  89.     while(now)
  90.     {
  91.         find(now,0);
  92.         if(dep[now]==dis[now]) r=now;
  93.         now=son[now];
  94.     }
  95.     while(l!=r && l)
  96.     {
  97.         l=father[l];
  98.         ++ans;
  99.     }
  100.     printf("%lld\n",ans);
  101.     return 0;
  102. }

View Code

谢谢大家！

版权声明：本文为mxrmxr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/mxrmxr/p/10049410.html