点分治奇异写法求条

#include<bits/stdc++.h>
using namespace std;
int n,m,q,vis[10005],minn,root[10005],rootx,sz[10005];
struct node{
	int ed,w;
};
vector<node>g[10005],tmp[10005]; 
bool cmp1(node x,node y){
	return x.w<y.w;
}
bool cmp2(node x,node y){
	return ((x.ed!=y.ed)?x.ed<y.ed:x.w<y.w);
}
void dfs(int x,int d,int fa,int fat,int siz,int fff){
	sz[x]=1;
	int maxn=0;
	tmp[fff].push_back({d,fat});
	for(int i=0;i<g[x].size();i++){
		if(g[x][i].ed!=fa&&!vis[g[x][i].ed]){
			dfs(g[x][i].ed,d,x,fat+g[x][i].w,siz,fff);
			maxn=max(maxn,sz[g[x][i].ed]);
			sz[x]+=sz[g[x][i].ed];
		}
	}
	maxn=max(maxn,siz-sz[x]);
	if(maxn<minn){
		minn=maxn;
		rootx=x;
	}
}
int dfs2(int x,int fa){
	int ans=1;
	for(int i=0;i<g[x].size();i++){
		if(g[x][i].ed!=fa&&!vis[g[x][i].ed]){
			ans+=dfs2(g[x][i].ed,x);
		}
	}
	return ans;
}
void init(int x){
	vis[x]=1;
	for(int i=0;i<g[x].size();i++){
		int ed=g[x][i].ed,w=g[x][i].w;
		if(!vis[ed]){
			minn=1e9;
			int siz=dfs2(ed,0);
			dfs(ed,i,0,w,siz,x);
			root[g[x][i].ed]=rootx;
			init(rootx);
		}
	}
}
bool solve(int x){
	int ans=0;
	vis[x]=1;
	for(int i=0;i<g[x].size();i++){
		int ed=g[x][i].ed,w=g[x][i].w;
		if(!vis[ed]){
			ans|=solve(root[g[x][i].ed]);
			if(ans)return 1;
		}
	}
	sort(tmp[x].begin(),tmp[x].end(),cmp1);
	for(int i=0;i<tmp[x].size();i++){
		ans|=(tmp[x][i].w==q);
		if(ans)return 1;
	}
	int cnt=0;
	for(int i=0,j=tmp[x].size(),k=tmp[x].size();i<tmp[x].size()&&j>=0&&k>=0;i++){
		while(j>0&&tmp[x][j-1].w>=q-tmp[x][i].w)j--;
		while(k>0&&tmp[x][k-1].w>q-tmp[x][i].w)k--;
		if(j<tmp[x].size()&&tmp[x][i].w+tmp[x][j].w==q&&tmp[x][i].w+tmp[x][k-1].w==q){
			cnt+=k-j;
		}
	}
	sort(tmp[x].begin(),tmp[x].end(),cmp2);
	int lst=0;
	for(int i=1;i<=tmp[x].size();i++){
		if(i==tmp[x].size()||tmp[x][i].ed!=tmp[x][i-1].ed){
			for(int j=lst,k=i,l=i;j<i;j++){
				while(k>lst&&tmp[x][k-1].w>=q-tmp[x][j].w)k--;
				while(l>lst&&tmp[x][l-1].w>q-tmp[x][j].w)l--;
				if(k<i&&tmp[x][j].w+tmp[x][k].w==q&&tmp[x][j].w+tmp[x][l-1].w==q){
					cnt-=l-k;
				}
			}
			lst=i;
		}
	}
	return cnt>0||ans;
}
int main(){
	cin>>n>>m;
	for(int i=1,u,v,w;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	init(1);
	for(int i=1;i<=m;i++){
		memset(vis,0,sizeof(vis));
		cin>>q;
		if(solve(1)){
			cout<<"AYE\n";
		}else{
			cout<<"NAY\n";
		}
	}
	return 0;
}