HDU 4607 Park Visit 两次DFS求树直径

两次DFS求树直径方法见 这里。

这里的直径是指最长链包含的节点个数，而上一题是指最长链的路径权值之和，注意区分。

K <= R: ans = K − 1;

K > R:   ans = R − 1 + ( K − R ) ∗ 2;

1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 const int MAXN = 100010;
  9 
 10 struct node
 11 {
 12     int v;
 13     int next;
 14 };
 15 
 16 int N, Q, EdgeN;
 17 int head[MAXN];
 18 int best[MAXN];
 19 int dp[MAXN][3];
 20 node D[ MAXN << 1 ];
 21 bool vis[MAXN];
 22 
 23 void AddEdge( int u, int v )
 24 {
 25     D[EdgeN].v = v;
 26     D[EdgeN].next = head[u];
 27     head[u] = EdgeN++;
 28     return;
 29 }
 30 
 31 void DFS1( int u )
 32 {
 33     vis[u] = true;
 34     for ( int i = head[u]; i != -1; i = D[i].next )
 35     {
 36         int v = D[i].v;
 37         int w = 1;
 38         if ( !vis[v] )
 39         {
 40             DFS1( v );
 41             if ( dp[v][0] + w > dp[u][0] )
 42             {
 43                 dp[u][1] = dp[u][0];
 44                 dp[u][0] = dp[v][0] + w;
 45                 best[u] = v;
 46             }
 47             else if ( dp[v][0] + w > dp[u][1] )
 48                 dp[u][1] = dp[v][0] + w;
 49         }
 50     }
 51     return;
 52 }
 53 
 54 void DFS2( int u )
 55 {
 56     vis[u] = true;
 57     for ( int i = head[u]; i != -1; i = D[i].next )
 58     {
 59         int fa = D[i].v;
 60         int w = 1;
 61         if ( !vis[fa] )
 62         {
 63             dp[fa][2] = dp[u][2] + w;
 64         if ( fa == best[u] )
 65             dp[fa][2] = max( dp[fa][2], dp[u][1] + w );
 66         else dp[fa][2] = max( dp[fa][2], dp[u][0] + w );
 67         DFS2( fa );
 68         }
 69     }
 70     return;
 71 }
 72 
 73 int main()
 74 {
 75     int T;
 76     scanf( "%d", &T );
 77     while ( T-- )
 78     {
 79         scanf( "%d%d", &N, &Q );
 80         EdgeN = 0;
 81         memset( head, -1, sizeof(head) );
 82         for ( int i = 1; i < N; ++i )
 83         {
 84             int u, v;
 85             scanf( "%d%d", &u, &v );
 86             AddEdge( u, v );
 87             AddEdge( v, u );
 88         }
 89 
 90         memset( dp, 0, sizeof(dp) );
 91         memset( vis, false, sizeof(bool) * (N + 1) );
 92         DFS1( 1 );
 93         memset( vis, false, sizeof(bool) * (N + 1) );
 94         DFS2( 1 );
 95 
 96         int maxx = 0;
 97         for ( int i = 1; i <= N; ++i )
 98             maxx = max( maxx, max( dp[i][0], dp[i][2] ) );
 99         ++maxx;
100 
101         while ( Q-- )
102         {
103             int K;
104             scanf( "%d", &K );
105             if ( maxx >= K )
106                 printf( "%d\n", K - 1 );
107             else printf( "%d\n", maxx - 1 + ( K - maxx ) * 2 );
108         }
109     }
110     return 0;
111 }      

转载于:https://www.cnblogs.com/GBRgbr/p/3220455.html