点分治板子求调,subtask3全RE
查看原帖
点分治板子求调,subtask3全RE
157884
Glassy_Sky楼主2023/7/4 10:19

RT

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e4+5,maxm=100+5;

int n,m,k,idx=0,head[maxn],root=0,siz[maxn],rtSon=1e9;
int dis[maxn],disi;
bool ans[10000007],vis[maxn];
vector<int>ok;
struct edge {
	int u,v,w,next;
}e[maxn];

inline void Add(const int& u,const int& v,const int& w) {
	e[++idx]={u,v,w,head[u]};
	head[u]=idx;
	return ;
}

void find_root(int now,int father,int tot) {
	int Son=0;
	siz[now]=1;
	for(int i=head[now];i;i=e[i].next) {
		int son=e[i].v;
		if(son==father||vis[son]) continue;
		find_root(son,now,tot);
		if(siz[son]>Son) Son=siz[son];
		siz[now]+=siz[son];
	}
	if(tot-siz[now]>Son) Son=tot-siz[now];
	if(Son<rtSon) root=now,rtSon=siz[Son];
	return ;
}

void get_dis(int now,int father,int distance) {
	dis[++disi]=distance;
	siz[now]=1;
	for(int i=head[now];i;i=e[i].next) {
		int son=e[i].v;
		if(son==father||vis[son]) continue;
		get_dis(son,now,distance+e[i].w);
		siz[now]+=siz[son];
	}
	return ;
}

void solve(int now,int father,int tot) {
	rtSon=1e9;
	find_root(now,father,tot);
	dis[1]=0;
	vis[root]=true;
	ok.push_back(0);
	for(int i=head[root];i;i=e[i].next) {
		int son=e[i].v;
		if(vis[son]) continue;
		disi=1;
		get_dis(son,root,e[i].w);
		for(int j=1;j<=disi;j++)
			for(int k=0;k<ok.size();k++)
				if(dis[j]+ok[k]<=1e7) ans[dis[j]+ok[k]]=true;
		for(int j=2;j<=disi;j++)
			ok.push_back(dis[j]);
	}
	ok.clear();
	for(int i=head[root];i;i=e[i].next) {
		int son=e[i].v;
		if(son==father||vis[son]) continue;
		solve(son,root,siz[son]);
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		Add(u,v,w);
		Add(v,u,w);
	}
	solve(1,0,n);
	ans[0]=true;
	while(m--) {
		int x;
		scanf("%d",&x);
		if(ans[x]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}
2023/7/4 10:19
加载中...