https://www.luogu.com.cn/problem/P3806
时隔一年半复习一下点分治。。。。
点分治模板就是nlogn的，然后内部每次要排序还要二分就是nlog^2n的复杂度。。。。812ms飘过
不过看到网上一些平方求是否有K的组合也过了？？？
显然是要先合并值相同的，再枚举一个值为x的，二分找k-x的吧。。。。
#include<bits/stdc++.h>
using namespace std;
const int maxl=1e4+10;
int n,m,cnt,k,tot,ans;
int ehead[maxl],dis[maxl],aa[maxl];
struct node
{
int val,num;
}a[maxl];
struct ed
{
int to,nxt,l;
}e[maxl<<1];
bool vis[maxl];
struct centertree
{
int n,ans,mini;
int son[maxl];
inline void dfs(int u,int fa)
{
son[u]=1;int v,res=0;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(v==fa || vis[v]) continue;
dfs(v,u);
son[u]+=son[v];
res=max(res,son[v]);
}
res=max(res,n-son[u]);
if(res<mini)
ans=u,mini=res;
}
int getcenter(int x)
{
ans=0;mini=2e9;
dfs(x,0);
return ans;
}
}tree;
inline void add(int u,int v,int l)
{
e[++cnt].to=v;e[cnt].l=l;
e[cnt].nxt=ehead[u];ehead[u]=cnt;
}
inline void prework()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
ehead[i]=0;
cnt=0;int u,v,l;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%d",&u,&v,&l);
add(u,v,l);add(v,u,l);
}
}
inline void getdis(int u,int fa)
{
aa[++aa[0]]=dis[u];
int v;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(v==fa || vis[v]) continue;
dis[v]=dis[u]+e[i].l;
getdis(v,u);
}
}
inline int find(int x)
{
if(x<k-x || x>a[tot].val) return 0;
int l=1,r=tot,mid;
while(l+1<r)
{
mid=(l+r)>>1;
if(a[mid].val>x)
r=mid;
else
l=mid;
}
if(a[l].val==x)
return a[l].num;
else if(a[r].val==x)
return a[r].num;
else
return 0;
}
inline int calc(int u,int w)
{
dis[u]=w;aa[0]=0;
getdis(u,0);
sort(aa+1,aa+1+aa[0]);
tot=1;a[1].val=aa[1];a[1].num=1;
for(int i=2;i<=aa[0];i++)
if(aa[i]!=a[tot].val)
a[++tot].val=aa[i],a[tot].num=1;
else
a[tot].num++;
int sum=0;
for(int i=1;i<=tot;i++)
{
if(a[i].val==k)
sum+=a[i].num*(a[i].num-1)/2;
if(a[i].val>=k-a[i].val)
break;
sum+=a[i].num*find(k-a[i].val);
}
return sum;
}
inline void solv(int u)
{
vis[u]=true;
ans+=calc(u,0);
int v;
for(int i=ehead[u];i;i=e[i].nxt)
{
v=e[i].to;
if(vis[v]) continue;
ans-=calc(v,e[i].l);
tree.n=tree.son[v];
int rt=tree.getcenter(v);
solv(rt);
}
}
inline void mainwork()
{
int rt;
for(int i=1;i<=m;i++)
{
scanf("%d",&k);
for(int j=1;j<=n;j++)
vis[j]=false;
tree.n=n;ans=0;
rt=tree.getcenter(1);
solv(rt);
if(ans>0)
puts("AYE");
else
puts("NAY");
}
}
int main()
{
prework();
mainwork();
return 0;
}