求看复杂度玄关

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int inf=2e8;
vector<int> G[N];
bool res[N];
bool vis[N];
int siz[N];
long long dp[N];
long long k[N];
int ans,x;
int all=0;
int n,q;
map<pair<int,int>,int> w;
map<long long,bool> m1;
void getG(int u,int fa)
{
	siz[u]=1;
	int p=0;
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i]==fa||vis[G[u][i]]) continue;
		getG(G[u][i],u);
		siz[u]+=siz[G[u][i]];
		p=max(siz[G[u][i]],p);
	}
	p=max(p,all-siz[u]);
	if(p<x) 
	{
		ans=u,x=p;
	}
	return;
}
void dfs2(int u,int fa)
{
	dp[u]=w[make_pair(u,fa)]+dp[fa];
//	cout<<u<<' '<<dp[u]<<'\n';
	for(int i=1;i<=q;i++)
	{
		if(m1[k[i]-dp[u]])
		{
			res[i]=1;
		}	
	}
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i]==fa||vis[G[u][i]]) continue;
		dfs2(G[u][i],u);
		
	}
	return;
}
void dfs3(int u,int fa)
{
	siz[u]=1;
	int p=0;
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i]==fa||vis[G[u][i]]) continue;
		dfs3(G[u][i],u);
		siz[u]+=siz[G[u][i]];
	}
	m1[dp[u]]=1;
	return;
}
void dfs(int u,int fa)
{
	m1[0]=1;
	dp[u]=0;
	siz[u]=0;
	vis[u]=1;
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i]==fa||vis[G[u][i]]) continue;
		dfs2(G[u][i],u);
		dfs3(G[u][i],u);
		
	}
	m1.clear();
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i]==fa||vis[G[u][i]]) continue;
		ans=0,x=inf;
		all=siz[G[u][i]];
		getG(G[u][i],u);
		dfs(ans,ans);
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		int u,v,w1;
		cin>>u>>v>>w1;
		G[u].push_back(v);
		G[v].push_back(u);
		w[make_pair(u,v)]=w[make_pair(v,u)]=w1;
	}
	for(int i=1;i<=q;i++) cin>>k[i];
	dfs(1,1);
	for(int i=1;i<=q;i++)
	{
		if(res[i]) cout<<"AYE\n";
		else cout<<"NAY\n";
	}
	return 0;
}