点分治60pts求条
查看原帖
点分治60pts求条
999274
CNS_5t0_0r2楼主2024/4/19 13:51
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9,M = 109,K = 1e7 + 9;
int n,m;
struct edge{
	int to,cost,nex;
} e[N << 1];
int head[N],ecnt;
void addedge(int u,int v,int w){
	ecnt++;
	e[ecnt] = (edge){v,w,head[u]};
	head[u] = ecnt;
}
int dp[N],siz[N],dis[N];
int rec[N],rec_top;//记录出现过的距离
int tmp[K],tmp_top;
bool vis[N];
int query[M];
bool exist[K],ans[M];
int tot,Center;
void get_center(int u,int fa){//寻找重心 
	dp[u] = 0;siz[u] = 1;
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to,w = e[i].cost;
		if(vis[v] || v == fa)
			continue;
		get_center(v,u);
		siz[u] += siz[v];
		dp[u] = max(dp[u],siz[v]);
	}
	if(max(dp[u],tot - siz[u]) < dp[Center])
		Center = u;
}
void get_dis(int u,int fa){//获得子树所有节点及到根的距离 
	rec[++rec_top] = dis[u];
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to,w = e[i].cost;
		if(vis[v] || v == fa)
			continue;
		dis[v] = dis[u] + w;
		get_dis(v,u);
	}
}
void merge(int u){//合并答案 
	tmp_top = 0;
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to,w = e[i].cost;
		if(vis[v])
			continue;
		rec_top = 0;dis[v] = w;
		get_dis(v,u);
		for(int j = 1;j <= rec_top;j++)
			for(int k = 1;k <= m;k++)
				if(query[k] >= rec[j])
					ans[k] |= exist[query[k] - rec[j]];
		for(int j = 1;j <= rec_top;j++){
			tmp[++tmp_top] = rec[j];
			exist[rec[j]] = true;
		}
	}
	for(int i = 1;i <= tmp_top;i++)
		exist[tmp[i]] = false;
}
void solve(int u){//点分治主体 
	vis[u] = true;
	merge(u);
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to,w = e[i].cost;
		if(vis[v])
			continue;
		dp[0] = n;Center = 0;tot = siz[v];
		get_center(v,u);
		solve(Center);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i < n;i++){
		int u,v,w;
		cin >> u >> v >> w;
		addedge(u,v,w);
		addedge(v,u,w);
	}
	for(int i = 1;i <= m;i++)
		cin >> query[i];
	dp[0] = tot = n;
	get_center(1,0);
	exist[0] = true;
	solve(Center);
	for(int i = 1;i <= m;i++)
		cout << (ans[i] ? "AYE" : "NAY") << '\n';
	return 0;
}
2024/4/19 13:51
加载中...