给定一颗n个节点树,边权为1,树上有m个点被标记,问从树上一个点出发,经过所有被标记的点的最短路程(起终点自选)。同时输出可能开始的编号最小的那个点。M<=N<=123456。
先想:如果所有点都被标记那么怎么样?我们发现对于起点s终点t,如果它们在同一条链上,那么必须先从s往外走,再回来,再经过t,再回到t。走过的路径就是树上所有边*2-s到t的路径。如果它们不在同一条链上,那么s在走到t的过程中访问所有点,走过的路径还是树上所有边*2-s到t的路径。
于是如果所有点都被标记,我们应该找到树的直径。如何找树的直径呢?先随便找一个点,然后找从这个点出发能到达的最远点。这个最远点一定是直径的一段,然后再找一次直径即可。(待证)
所以我们只需要把这棵树转成全被标记的就行了。我们随便找一个标记过的点,将其作为树的根,然后只保留标记各个点所在的那条链的上端,因为它们是唯一且一定会经过的边。然后按照算法来就行了。
但这样做还不够,题目还要求输出可能开始的编号最小的那个点。我们发现如果第一次从根开始找,编号最小的点要么是离根最远的点,要么是离根最远的点所找到的最远的点。而离根最远的点能找到的最远的点实际上都是一样的,这就告诉我们直接取最小编号的点,再找一遍,再取最小值就行了。
给出我丑陋的代码:
#include#include #include #include using namespace std;const int maxn=125000;int n, m, root, printed_num, longest_road;int printed_list[maxn], printed[maxn], visited[maxn], step[maxn];vector node[maxn], sons[maxn];queue q;int make_tree(int pos){ int return_value=0, t=0, nowson; visited[pos]=1; for (int i=0; i farthest){ farthest=step[nownode]; farone=nownode; } if (step[nownode]==farthest&&farone>nownode) farone=nownode; } int a, b; a=farone; farthest=0, farone=0; while (!q.empty()) q.pop(); memset(visited, 0, sizeof(visited)); memset(step, 0, sizeof(step)); q.push(a); while (!q.empty()){ nownode=q.front(); q.pop(); visited[nownode]=1; for (int i=0; i farthest){ farthest=step[nownode]; farone=nownode; } if (step[nownode]==farthest&&farone>nownode) farone=nownode; } b=farone; if (a