边分治

边分治是类似点分治的一种树分治方法。顾名思义，边分治就是用边来分治。我们每次找的边也就是两边 size 最大值尽量小的边。同样的，边分治的过程也是把树分成了很多联通块，只是对边打标记罢了。

但是，直接边分复杂度是假的，可以参考菊花图直接卡成 $O(n^2)$ 。我们可以对所有儿子分别建立一个虚点，从上一个儿子的虚点向下一个儿子的虚点连 $0$ 边。这样做后会发现所有点的度数都变成了 $3$ ，所以称之为三度化。

三度化后边分治的过程中的时间复杂度分析大概是 $T(n) = O(n) + T(\frac 1 3 n) + T(\frac 2 3 n)$ 这个东西，最后也是 $O(n\log n)$ 。

边分治的优势在于每次分治只有两个子树，自然不需要像点分那样考虑容斥或者合并子树之类的增加常数，而且也更好写。但是其劣势也很明显，如果条件没办法三度化这个东西显然就做不了了。

下面是边分版本的点分治模版。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 400006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define min( a , b ) ( (a) < (b) ? (a) : (b) )
#define max( a , b ) ( (a) > (b) ? (a) : (b) )
#define P 998244353
typedef long long ll;
int n , m , N;

int head[MAXN << 1], nex[MAXN << 2], to[MAXN << 2], wto[MAXN << 2], ecn = -1;

void ade(int u, int v, int w) {
//    cout << u << ' ' << v << ' ' << w << endl;
    to[++ecn] = v, nex[ecn] = head[u], head[u] = ecn, wto[ecn] = w;
    to[++ecn] = u, nex[ecn] = head[v], head[v] = ecn, wto[ecn] = w;
}

vector<pii> G[MAXN];

void rebuild( int u , int fa ) {
    int flg = 0 , cur = 0 , last = u;
    for( auto& t : G[u] ) {
        int v = t.fi;
        if( v == fa ) continue;
        if( !flg ) { flg = 1; ade( u , v , t.se ); }
        else {
            cur = ++ n;
            ade( last , cur , 0 ) , ade( cur , v , t.se );
            last = cur;
        }
        rebuild( v , u );
    }
}

int vis[MAXN << 1] , siz[MAXN << 1] , E , rt , mn;
void getsize( int u , int fa ) {
    siz[u] = 1;
    for( int i = head[u] ; ~i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa || vis[i >> 1] ) continue;
        getsize( v , u );
        siz[u] += siz[v];
    }
}
void getedge( int u , int fa ) {
    for( int i = head[u] ; ~i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa || vis[i >> 1] ) continue;
        if( max( siz[v] , siz[rt] - siz[v] ) < mn ) mn = max( siz[v] , siz[rt] - siz[v] ) , E = ( i >> 1 );
        getedge( v , u );
    }
}
int getit( int u ) { // the edge (ret << 1) and (ret << 1 | 1) are the answer.
    rt = u , mn = 0x3f3f3f3f , E = -1; getsize( u , u ); getedge( u , u ); return E;
}

int que[MAXN] , ans[MAXN];

int dis[MAXN] , buc[10000006];
vi pts;
void work1( int u , int fa ) {
    if( dis[u] <= 10000000 ) buc[dis[u]] = 1 , pts.pb( u );
    for( int i = head[u] ; ~i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa || vis[i >> 1] ) continue;
        dis[v] = dis[u] + wto[i];
        work1( v , u );
    }
}
void work2( int u , int fa ) {
    rep( i , 1 , m ) ans[i] += dis[u] <= que[i] ? buc[que[i] - dis[u]] : 0;
    for( int i = head[u] ; ~i ; i = nex[i] ) {
        int v = to[i];
        if( v == fa || vis[i >> 1] ) continue;
        dis[v] = dis[u] + wto[i];
        work2( v , u );
    }
}

void solve( int e ) {
    vis[e] = 1;
    int u = to[e << 1] , v = to[e << 1 | 1];
    pts.clear();
    dis[u] = wto[e << 1] , work1( u , u );
    dis[v] = 0; work2( v , v );
    for( int x : pts ) buc[dis[x]] = 0;
    u = getit( u ) , v = getit( v );
    if( ~u ) solve( u );
    if( ~v ) solve( v );
}

void solve() {
    memset( head , -1 , sizeof head );
    cin >> n >> m; N = n;
    int u , v , w;
    rep( i , 2 , n ) scanf("%d%d%d",&u,&v,&w) , G[u].eb( mp( v , w ) ) , G[v].eb( mp( u , w ) );
    rep( i , 1 , m ) scanf("%d",que + i);
    rebuild( 1 , 1 );
    solve( getit( 1 ) );
    rep( i , 1 , m ) if( ans[i] ) puts("AYE"); else puts("NAY");
}

signed main() {
//    freopen("P3806_8.in","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}