对每个重心保存，依次遍历子树，记录下距离为d的深度最小的路径，在遍历时用遍历过的其它子树更新答案。

 

收获：

对于当前子树，可以写两个遍历函数，一个用于更新答案，一个用于更新维护的信息。

 

1 /**************************************************************  2     Problem: 2599  3     User: idy002  4     Language: C++  5     Result: Accepted  6     Time:17708 ms  7     Memory:24900 kb  8 ****************************************************************/  9   10 #include 
      
        11 #include 
       
         12 #define oo 0x3f3f3f3f 13 #define N 200010 14 #define M 1000010 15   16 int n, m, ans; 17 int head[N], dest[N+N], wght[N+N], next[N+N], ntot; 18 int vis[N], fat[N], siz[N], bac[N], dis[N], dep[N], tot_siz, cur_root; 19 int vv[M]; 20 int stk[N], tp; 21   22 void insert( int u, int v, int w ) { 23     ntot++; 24     next[ntot] = head[u]; 25     wght[ntot] = w; 26     dest[ntot] = v; 27     head[u] = ntot; 28 } 29   30 void dfs_root( int u ) { 31     siz[u]=1, bac[u]=0; 32     for( int t=head[u]; t; t=next[t] ) { 33         int v=dest[t]; 34         if( vis[v] || v==fat[u] ) continue; 35         fat[v] = u; 36         dfs_root(v); 37         siz[u] += siz[v]; 38         if( siz[v]>bac[u] ) bac[u]=siz[v]; 39     } 40     if( tot_siz-siz[u]>bac[u] ) bac[u]=tot_siz-siz[u]; 41     if( bac[cur_root]>bac[u] ) cur_root=u; 42 } 43 void dfs_read( int u ) { 44     if( m-dis[u]<0 ) return; 45     if( ans > vv[m-dis[u]]+dep[u] ) 46         ans = vv[m-dis[u]]+dep[u]; 47     for( int t=head[u]; t; t=next[t] ) { 48         int v=dest[t], w=wght[t]; 49         if( vis[v] || v==fat[u] ) continue; 50         dis[v]=dis[u]+w; 51         dep[v]=dep[u]+1; 52         fat[v]=u; 53         dfs_read(v); 54     } 55 } 56 void dfs_write( int u ) { 57     if( m-dis[u]<0 ) return; 58     if( vv[dis[u]]>dep[u] ) { 59         vv[dis[u]]=dep[u]; 60         stk[++tp] = dis[u]; 61     } 62     for( int t=head[u]; t; t=next[t] ) { 63         int v=dest[t]; 64         if( vis[v] || v==fat[u] ) continue; 65         dfs_write(v); 66     } 67 } 68 void bfs( int rt ) { 69     tot_siz = siz[rt]; 70     cur_root = 0; 71     fat[rt] = rt; 72     dfs_root( rt ); 73       74     rt = cur_root; 75     vis[rt] = true; 76   77     vv[0] = 0; 78     stk[tp=1] = 0; 79     for( int t=head[rt]; t; t=next[t] ) { 80         int v=dest[t], w=wght[t]; 81         if( vis[v] ) continue; 82         fat[v] = rt; 83         dis[v] = w; 84         dep[v] = 1; 85         dfs_read(v); 86         dfs_write(v); 87     } 88     while( tp ) vv[stk[tp--]] = oo; 89   90     for( int t=head[rt]; t; t=next[t] ) { 91         int v=dest[t]; 92         if( vis[v] ) continue; 93         bfs(v); 94     } 95 } 96 void build_vdcp() { 97     bac[0] = siz[1] = n; 98     memset( vv, 0x3f, sizeof(vv) ); 99     ans = oo;100     bfs( 1 );101 }102  103 int main() {104     scanf( "%d%d", &n, &m );105     for( int i=1,u,v,w; i