树上启发式合并实（强）现（上）点分治模板题

点分治？没听说过，还是写一发DSU On Tree（树上启发式合并）好了~

个人拙见，DSU On Tree主要是解决一些静态的子树信息查询的问题，当然通过一些骚操作可以拓展。拓展到路径最常见的套路就是强制该路径经过当前子树根节点，然后DFS枚举每个点作为根节点。

点分治的思想主要是寻找重心作为根节点以优化复杂度，启发式的思想则类似树链剖分，每次计算贡献时先枚举轻儿子，计算后清除贡献，最后枚举重儿子，计算后保留重儿子的信息，最后依次枚举轻儿子，暴力将答案计入贡献。这样的复杂度是的。

然而只写这么多过不了审核，所以接下来仔细解释一下算法的原理！因为网上其他的教程都太简短了！所以我才学了一整天！

首先到底为什么要清空轻儿子的贡献：比如本模板题中，我们找的是强制经过当前根节点的路径，所以我们要避免同一个子树内的节点互相乱访问，才要清空轻儿子的贡献。

然后就是这种做法的复杂度为什么能保证？因为对于每个轻儿子我都要使用一次暴力，所以每个点被暴力的次数是它头顶上轻儿子的个数。根据树链剖分的基本常识，每个点到根节点的轻点个数是级别的，所以所有点被访问的总次数是，算法的复杂度是。

然后这个算法比点分治好的地方在于：编码特别简单，调试特别简单，而且普通数据下的复杂度一定比点分治要好（因为每个点头顶的轻儿子个数远少于），尤其是链的情况下，DSU On Tree更是只要线性复杂度。

放一下代码（不开O2，57ms）：

#include <bits/stdc++.h>
#define lld I64d
using namespace std ;
inline long long Readin() {
    long long K = 0 , F = 1 ; char C = ' ' ;
    while( C < '0' or C > '9' ) F = C == '-' ? -1 : 1 , C = getchar() ;
    while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ;
    return F * K ;
}
const int MaxQ = 100 + 10 ;
const int MaxN = 10000 + 10 ;
const int MaxM = 20000 + 10 ;
const int MaxK = 10000000 + 10 ;
int N , Q , Asks[MaxQ] ;
bool Anss[MaxQ] ;
int Cnt , Head[MaxN] , To[MaxM] , Next[MaxM] , Val[MaxM] ;
inline void Add( int U , int V , int W ) {
    Next[++Cnt] = Head[U] ;
    Head[U] = Cnt ;
    To[Cnt] = V ;
    Val[Cnt] = W ;
}
int Fa[MaxN] , Size[MaxN] , D[MaxN] , Hson[MaxN] ;
bool Apr[MaxK] ;
int Depp ;
void Dfs( int Nod ) {
    Size[Nod] = 1 ;
    for(register int i = Head[Nod] ; i ; i = Next[i] ) 
        if( To[i] ^ Fa[Nod] ) {
            Fa[To[i]] = Nod ;
            D[To[i]] = D[Nod] + Val[i] ;
            Dfs( To[i] ) ;
            if( Size[To[i]] > Size[Hson[Nod]] ) Hson[Nod] = To[i] ;
            Size[Nod] += Size[To[i]] ;
        }
}
inline void C( int Nod ) {
    for(register int i = 0 ; ++i <= Q ; )
        if( Asks[i] - D[Nod] + Depp >= 0 )
            Anss[i] |= Apr[Asks[i]-D[Nod]+Depp] ;
}
void Calc( int Nod ) {
    C( Nod ) ;
    for(register int i = Head[Nod] ; i ; i = Next[i] )
        if( To[i] ^ Fa[Nod] ) Calc( To[i] ) ;
}
void Upd( int Nod ) {
    Apr[D[Nod]] = true ;
    for(register int i = Head[Nod] ; i ; i = Next[i] )
        if( To[i] ^ Fa[Nod] ) Upd( To[i] ) ;
}
void Clear( int Nod ) {
    Apr[D[Nod]] = false ;
    for(register int i = Head[Nod] ; i ; i = Next[i] )
        if( To[i] ^ Fa[Nod] ) Clear( To[i] ) ;
}
void Dfs( int Nod , bool Tag ) {
    for(register int i = Head[Nod] ; i ; i = Next[i] )
        if( To[i] ^ Fa[Nod] and To[i] ^ Hson[Nod] ) Dfs( To[i] , true ) ;
    if( Hson[Nod] ) Dfs( Hson[Nod] , false ) ;
    Depp = D[Nod] << 1 ;
    Apr[D[Nod]] = true ;
    C( Nod ) ;
    for(register int i = Head[Nod] ; i ; i = Next[i] )
        if( To[i] ^ Fa[Nod] and To[i] ^ Hson[Nod] ) Calc( To[i] ) , Upd( To[i] ) ;
    if( Tag ) Clear( Nod ) ;
}
int main() {
    N = Readin() ;
    Q = Readin() ;
    for(register int i = 0 , U , V , W ; ++i < N ; ) {
        U = Readin() ;
        V = Readin() ;
        W = Readin() ;
        Add( U , V , W ) ;
        Add( V , U , W ) ;
    }
    for(register int i = 0 ; ++i <= Q ; Asks[i] = Readin() ) ;
    Dfs( 1 ) ;
    Dfs( 1 , false ) ;
    for(register int i = 0 ; ++i <= Q ; puts( Anss[i] ? "AYE" : "NAY" ) ) ;
    return 0 ;
}
/*
5 3
1 2 1
1 3 1
2 4 2
2 5 2
1 2 3
*/