[关闭]
@ysner 2018-06-05T11:58:26.000000Z 字数 2104 阅读 1690

[APIO2010]巡逻

树的直径


题面

给定一颗树,现可加入)条边,问在加边后,从号节点出发走遍所有点再回到号点最小距离是多少?

解析

(前置定义:实边:本来就存在的边;虚边:新加的条边之一;)

的范围耐人寻味,可以尝试用分类讨论完成此题。

没加边时,最小距离是边数×2
要减距离就从这些实边上来。
加了一条虚边(不是自环)后,整个图转变为一个环套树。
环越大,距离越小。
如何让环的大小最大?
把树的直径两端连起来即可。
这时最小距离改变为环的大小+环外边数×2
减少的距离为环的大小-2(因在加边之前,环其它边对距离的贡献为(环的大小-1)×2,加完后变为环的大小)。
同时等价于树的直径-1

这时我们要在环套树上加一条虚边。
再加一条边,会引起什么改变呢?

虚边两端点都在环外

这肯定是更优的,减少的距离还是树的直径-1。(代表新加入的虚边)

虚边一端点在环内

这样会形成两个有公共边的环。
要符合要求地走完它,就要额外把公共边多走一遍。(画图理解)
则距离减少量为-公共边数量+新纳入环的实边数-1(代表新加入的虚边)

虚边两端点都在环内

这种情况貌似是上一种的特殊情况。
因为新纳入环的实边数=0
所以这种做法是不存在的。

实现

发现式子可以合并,
肯定先找一遍树的直径。
然后把在环中的实边边权标为,再找一遍。
注意到这次就不能用bfs找直径了,只能用DP,反正不用找出树的直径上的边
找出的直径是不是正数,说明加边肯定亏,那就加自环吧。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=1e5+100;
  14. int n,k,h[N],cnt=1,mx,pos,dis[N],ans;
  15. bool vis[N];
  16. struct Edge{int to,next,w;}e[N<<1];
  17. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u],1};h[u]=cnt;}
  18. il int gi()
  19. {
  20. re int x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il void dpdp(re int u)
  28. {
  29. vis[u]=1;
  30. for(re int i=h[u];i+1;i=e[i].next)
  31. {
  32. re int v=e[i].to;
  33. if(vis[v]) continue;
  34. dpdp(v);
  35. mx=max(mx,dis[u]+dis[v]+e[i].w);
  36. dis[u]=max(dis[u],dis[v]+e[i].w);
  37. }
  38. }
  39. il void dfs(re int u,re int len)
  40. {
  41. vis[u]=1;if(len>mx) mx=len,pos=u;dis[u]=len;
  42. for(re int i=h[u];i+1;i=e[i].next)
  43. {
  44. re int v=e[i].to;
  45. if(vis[v]) continue;
  46. dfs(v,len+e[i].w);
  47. }
  48. vis[u]=0;
  49. }
  50. il int dfsb(re int u)
  51. {
  52. if(!dis[u]) return 1;
  53. for(re int i=h[u];i+1;i=e[i].next)
  54. {
  55. re int v=e[i].to;
  56. if(dis[v]==dis[u]-1)
  57. if(dfsb(v)) {e[i].w=e[i^1].w=-1;return 1;}
  58. }
  59. return 0;
  60. }
  61. int main()
  62. {
  63. memset(h,-1,sizeof(h));
  64. n=gi();k=gi();ans=(n-1)*2;
  65. fp(i,1,n-1)
  66. {
  67. re int u=gi(),v=gi();
  68. add(u,v);add(v,u);
  69. }
  70. dfs(pos=1,0);//第一次找直径的第一遍DFS
  71. mx=-1e9;memset(dis,0,sizeof(dis));
  72. dfs(pos,0);//第一次找直径的第二遍DFS
  73. ans-=mx-1;
  74. if(k==1) {printf("%d\n",ans);return 0;}
  75. dfsb(pos);//给在直径上的边标号
  76. mx=0;memset(vis,0,sizeof(vis));memset(dis,0,sizeof(dis));
  77. dpdp(1);//第二次找直径
  78. ans-=mx-1;
  79. printf("%d\n",ans);
  80. return 0;
  81. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注