两次DFS求树直径方法见 这里。
这里的直径是指最长链包含的节点个数，而上一题是指最长链的路径权值之和，注意区分。
K <= R: ans = K − 1;
K > R: ans = R − 1 + ( K − R ) ∗ 2;
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> using namespace std; const int MAXN = ; struct node
{
int v;
int next;
}; int N, Q, EdgeN;
int head[MAXN];
int best[MAXN];
int dp[MAXN][];
node D[ MAXN << ];
bool vis[MAXN]; void AddEdge( int u, int v )
{
D[EdgeN].v = v;
D[EdgeN].next = head[u];
head[u] = EdgeN++;
return;
} void DFS1( int u )
{
vis[u] = true;
for ( int i = head[u]; i != -; i = D[i].next )
{
int v = D[i].v;
int w = ;
if ( !vis[v] )
{
DFS1( v );
if ( dp[v][] + w > dp[u][] )
{
dp[u][] = dp[u][];
dp[u][] = dp[v][] + w;
best[u] = v;
}
else if ( dp[v][] + w > dp[u][] )
dp[u][] = dp[v][] + w;
}
}
return;
} void DFS2( int u )
{
vis[u] = true;
for ( int i = head[u]; i != -; i = D[i].next )
{
int fa = D[i].v;
int w = ;
if ( !vis[fa] )
{
dp[fa][] = dp[u][] + w;
if ( fa == best[u] )
dp[fa][] = max( dp[fa][], dp[u][] + w );
else dp[fa][] = max( dp[fa][], dp[u][] + w );
DFS2( fa );
}
}
return;
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d%d", &N, &Q );
EdgeN = ;
memset( head, -, sizeof(head) );
for ( int i = ; i < N; ++i )
{
int u, v;
scanf( "%d%d", &u, &v );
AddEdge( u, v );
AddEdge( v, u );
} memset( dp, , sizeof(dp) );
memset( vis, false, sizeof(bool) * (N + ) );
DFS1( );
memset( vis, false, sizeof(bool) * (N + ) );
DFS2( ); int maxx = ;
for ( int i = ; i <= N; ++i )
maxx = max( maxx, max( dp[i][], dp[i][] ) );
++maxx; while ( Q-- )
{
int K;
scanf( "%d", &K );
if ( maxx >= K )
printf( "%d\n", K - );
else printf( "%d\n", maxx - + ( K - maxx ) * );
}
}
return ;
}