概念

點分治用于解決有一定要求的鏈的計數。

對于點 \(u\) 的子樹的問題，可以將答案分為：

1. 經過點 \(u\)

2. 不經過點 \(u\)

第一種可以用桶加暴力。枚舉一端的長度，用桶計算另一端長度；第二種分到子樹中解決即可。

注意到，在隨機選根的時候該算法表現不優秀，但若根為重心，因為每次子樹大小都減少一半，所以時間復雜度優秀，為 \(O(n\log n)\)。

代碼

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include<set>
#include<queue>
#define mod 998244353
#define int long long
using namespace std;
int n,m,ans[10001],ques[10001],use[10001],len,fin[10001],len2,ton[10000001],anss,mid,f[10001];
bool debug=false;
struct edge
{
	int v,w;
};
vector<edge> g[10001];
bool vis[10001];
void getmid(int u,int fa,int sz) //重心 
{
    if(u!=1 && g[u].size()==1) return; //葉子結點
    int ma=0;
    for(int i=0;i<g[u].size();i++)
    {
        if(g[u][i].v==fa||vis[g[u][i].v]) continue;
        getmid(g[u][i].v,u,sz);
        f[u]+=f[g[u][i].v]+1; //更新狀態
        ma=max(ma,f[g[u][i].v]); //最大子節點 
    }
    ma=max(ma+1,sz-f[u]-1);
    if(ma<anss) //如果小于當前 
    {
        anss=ma;
        mid=u;
    }
}
void init()
{
	for(int i=1;i<=len;i++)
	{
		ton[use[i]]=0; //清空桶
	}
	len=0;
}
void dfs(int u,int fa,int tot) //找值
{
	fin[++len2]=tot;
	for(int i=0;i<g[u].size();i++)
	{
		if(g[u][i].v==fa||vis[g[u][i].v]) continue;
		dfs(g[u][i].v,u,tot+g[u][i].w);
	}
}
int getsiz(int u,int fa) //因為換根，子樹大小要重新計算
{
	int ret=1;
	f[u]=0;
	for(int i=0;i<g[u].size();i++)
	{
		if(g[u][i].v==fa||vis[g[u][i].v]) continue;
		ret+=getsiz(g[u][i].v,u);
	}
	return ret;
}
void work(int u)
{
	for(int i=0;i<g[u].size();i++)
	{
		if(vis[g[u][i].v]) continue;
		len2=0;
		dfs(g[u][i].v,u,g[u][i].w);
		for(int z=1;z<=len2;z++)
		{
			for(int j=1;j<=m;j++)
			{
				if(ques[j]-fin[z]>=0&&ques[j]-fin[z]<=10000000)	ans[j]+=ton[ques[j]-fin[z]]; //有，計算一下
			}
		}
		for(int z=1;z<=len2;z++)
		{
			if(fin[z]>10000000) continue;
			ton[fin[z]]++;
			if(ton[fin[z]]==1) use[++len]=fin[z];
		}
	}
	for(int j=1;j<=m;j++)
	{
		ans[j]+=ton[ques[j]]; //單獨的鏈
	}
}
void dfz(int u)
{
	if(u!=1 && g[u].size()==1) return;
	anss=10000000000;
	mid=0;
	getmid(u,-1,getsiz(u,-1)); //重心
	init();
	u=mid; //換根
	work(u);
	vis[u]=true;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i].v;
		if(vis[v]) continue;
		dfz(v);
	}
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1,u,v,w;i<n;i++)
	{
		scanf("%lld%lld%lld",&u,&v,&w);
		g[u].push_back((edge){v,w});
		g[v].push_back((edge){u,w});
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&ques[i]);
	}
	dfz(1);
	for(int i=1;i<=m;i++)
	{
		cout<<(ans[i]==0?"NAY\n":"AYE\n");
	}
}