树的直径总结

2020-10-28 10:16:19 浏览数 (1)

1.树的直径的求法不是很难，两遍DFS，树的直径又称为最长路，没看到树的直径的裸题，除了饭店的那个题，讲的是有一家饭店在一个图中，饭店的送餐时间与最远的送餐距离成正比，求饭店的修建位置使得饭店的送餐时间最短，那么这个题就是说在图中赵找一条最长路，将饭店建在最长路的中心，这个题也是CCPC2019网络赛的一个题，几乎一样的模板，但是这个知识点常与树形DP一起出现，什么添边，什么附加条件，但是离不开最长路两边DFS，至于模板，就不放了，过两天整一个模板集。