AtCoder Grand Contest 001 C Shorten Diameter 树的直径知识

链接：http://agc001.contest.atcoder.jp/tasks/agc001_c

题解（官方）：

We use the following well-known fact about trees.
Let T be a tree, and let D be the diameter of the tree.

• If D is even, there exists an vertex v of T such that for each vertex w in
T, the distance between w and v is at most D/2.

• If D is odd, there exists an edge e of T such that for each vertex w in T,
the distance between w and one of the endpoints of e is at most (D −1)/2.
Here v and e are called centers of the tree.

The proof of this fact is not very hard. See the picture below. The blue
vertices are the endpoints of the diameters, and the red vertex (or edge) is in
the middle of the diameter. This red vertex is the center of the tree; if there
is a vertex v such that dist(v, red) > D/2, the distance between v and one of
blue points will be more than D (because the distance between the red point
and each blue point is D/2). The proof for odd case is similar.

Now the problem can be solved in the following way (we only describe the
solution for the even case, but the odd case is similar). Choose a vertex x in
the tree (this will be the center after removal of vertices) and count the number
of vertices y such that dist(x, y) > D/2. If we remove all such y, the diameter
of the remaining graph will be at most D. Thus, we can try all N vertices as x
and the answer is the minimum count of such y. The solution works in O(N^2).

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef long long LL;

const int N  = 2e3+;

const int INF = 0x3f3f3f3f;

const LL mod = 1e9+;

typedef pair<int ,int >pii;

struct Edge{

  int v,next;

}edge[N<<];

int head[N],tot,n,k;

void add(int u,int v){

  edge[tot].v=v;

  edge[tot].next=head[u];

  head[u]=tot++;

}

bool vis[N];

int d[N];

void bfs(int s,int f){

  queue<int>q;

  while(!q.empty())q.pop();

  d[s]=;vis[s]=true;

  q.push(s);

  while(!q.empty()){

     int u=q.front();

     q.pop();

     for(int i = head[u];~i;i=edge[i].next){

      int v=edge[i].v;

      if(vis[v]||v==f)continue;

      d[v]=d[u]+;

      vis[v]=true;

      q.push(v);

     }

  }

}

int solveodd(int u,int v){

   memset(d,INF,sizeof(d));

   memset(vis,,sizeof(vis));

   bfs(u,v);bfs(v,u);

   int ret=;

   for(int i=;i<=n;++i)

    if(d[i]>k)++ret;

   return ret;

}

int solveeven(int u){

   memset(d,INF,sizeof(d));

   memset(vis,,sizeof(vis));

   bfs(u,);

   int ret=;

   for(int i=;i<=n;++i)

    if(d[i]>k)++ret;

   return ret;

}

int main(){

  scanf("%d%d",&n,&k);

  memset(head,-,sizeof(head));

  for(int i=;i<=n-;++i){

    int u,v;

    scanf("%d%d",&u,&v);

    add(u,v);add(v,u);

  }

  int ret=INF;

  if(k&){

    k>>=;

    for(int i=;i<tot;i+=)

      ret=min(ret,solveodd(edge[i].v,edge[i+].v));

  }

  else{

    k>>=;

    for(int i=;i<=n;++i)

      ret=min(ret,solveeven(i));

  }

  printf("%d\n",ret);

  return ;

}

AtCoder Grand Contest 001 C Shorten Diameter 树的直径知识的相关教程结束。