求助点分治

rt，WA on #1,#4,#6。

#include <bits/stdc++.h>
using namespace std;

const int _ = 1e6 + 5;

int n , m , root , sum , tot;
int f[_] , siz[_] , dep[_] , vis[_] , ans[_] , Q[_];

struct Edge { int v , w , nxt ; } e[_];
int head[_] , ecnt;
void Add( int u , int v , int w ) { e[ ++ecnt ] = Edge{ v , w , head[ u ] } ; head[ u ] = ecnt ; }

void GetRoot( int x , int fa ) {
  f[ x ] = 0 , siz[ x ] = 1;
  for( int i = head[ x ] ; i ; i = e[ i ].nxt ) {
    int y = e[ i ].v;
    if( vis[ y ] || y == fa ) continue;
    GetRoot( y , x );
    siz[ x ] += siz[ y ];
    f[ x ] = max( f[ x ] , siz[ y ] );
  }
  f[ x ] = max( f[ x ] , sum - siz[ x ] );
  if( f[ x ] < f[ root ] ) root = x;
}

void GetDep( int x , int fa , int sum ) {
  dep[ ++tot ] = sum;
  for( int i = head[ x ] ; i ; i = e[ i ].nxt ) {
    int y = e[ i ].v;
    if( y == fa || vis[ y ] ) continue;
    GetDep( y , x , sum + e[ i ].w );
  }
}

void Calc( int x ) {
  tot = 0;
  GetDep( x , 0 , 0 );
  sort( dep + 1 , dep + 1 + tot );
  for( int i = 1 ; i <= m ; i++ ) {
    int l = 1 , r = tot;
    if( ans[ i ] ) continue;
    while( l < r ) {
      if( dep[ l ] + dep[ r ] > Q[ i ] ) r--;
      else if( dep[ l ] + dep[ r ] < Q[ i ] ) l++;
      else if( dep[ l ] == dep[ r ] ) {
        if( dep[ r ] == dep[ r - 1 ] ) r--;
        else l++;
      }
      else {
        ans[ i ] = 1;
        break;
      }
    }
  }
}

void Devide( int x ) {
  vis[ x ] = 1;
  Calc( x );
  for( int i = head[ x ] ; i ; i = e[ i ].nxt ) {
    int y = e[ i ].v;
    if( vis[ y ] ) continue;
    Calc( y );
    root = 0 , sum = siz[ y ];
    GetRoot( y , 0 );
    Devide( root );
  }
}

int main() {
  cin >> n >> m;
  for( int i = 1 , u , v , w ; i < n ; i++ ) {
    cin >> u >> v >> w;
    Add( u , v , w ) , Add( v , u , w );
  }
  for( int i = 1 ; i <= m ; i++ ) cin >> Q[ i ];
  sum = f[ 0 ] = n;
  GetRoot( 1 , 0 );
  Devide( root );
  for( int i = 1 ; i <= m ; i++ ) puts( ans[ i ] ? "AYE" : "NAY" );
  return 0;
}