求调
查看原帖
求调
411141
alpharchmage楼主2024/7/16 09:52
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n = 0 , m = 0 , cnt = 0 , root_now = 0 , sum_now = 0 , tot = 0 , tmp = 0;
array<int , 2000100> head , dis , vis , query , sizes , dp , solved , exist , del;
bitset<100000100> judged;
struct Node{
	int to;
	int val;
	int nxt;
};
array<Node , 2000100> edge;
void new_line(int a , int b , int c)
{
	edge.at(++ cnt).to = b;
	edge.at(cnt).nxt = head.at(a);
	edge.at(cnt).val = c;
	head.at(a) = cnt;
	return;
}
void get_root(int x , int fa)
{
	sizes.at(x) = 1;
	dp.at(x) = 0;
	for(int e = head.at(x);e;e = edge.at(e).nxt)
	{
		int to = edge.at(e).to;
		if(to != fa && !vis.at(to))
		{
			get_root(to , x);
			sizes.at(x) += sizes.at(to); 
			dp.at(x) = max(dp.at(x) , sizes.at(to));
		}
	}
	dp.at(x) = max(sizes.at(x) , sum_now - sizes.at(x));
	if(dp.at(x) < dp.at(root_now))
	{
		root_now = x;
	}
	return;
}
void init(int x , int fa)
{
	exist.at(++ tmp) = dis.at(x);
	for(int e = head.at(x);e;e = edge.at(e).nxt)
	{
		int to = edge.at(e).to;
		if(to != fa && !vis.at(to))
		{
			dis.at(to) = dis.at(x) + edge.at(e).val;
			init(to , x);
		} 
	}
}
void update(int x)
{
	tot = 0;
	for(int e = head.at(x);e;e = edge.at(e).nxt)
	{
		int to = edge.at(e).to;
		if(vis.at(to))
		{
			continue;
		}
		tmp = 0;
		dis.at(to) = edge.at(e).val;
		init(to , x);
		for(int i = tmp;i >= 1;-- i)
		{
			for(int k = 1;k <= m;++ k)
			{
				if(query.at(k) >= exist.at(i))
				{
					solved.at(k) |= judged.test(query.at(k) - exist.at(i));
				}
			}
		}
		for(int i = tmp;i >= 1;-- i)
		{
			del.at(++ tot) = exist.at(i);
			judged.set(exist.at(i)) = true;
		}
	}
	for(int i = 1;i <= tot;++ i)
	{
		judged.reset(del.at(i)) = false;
	}
}
void dfs(int x)
{
	vis.at(x) = true;
	judged.set(0);
	update(x);
	for(int e = head.at(e);e;e = edge.at(e).nxt)
	{
		int to = edge.at(e).to;
		if(!vis.at(to))
		{
			root_now = 0;
			dp.at(root_now) = INT_MAX;
			sum_now = sizes.at(x);
			get_root(to , -1);
			dfs(root_now);
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1;i <= (n - 1);++ i)
	{
		int x = 0 , y = 0 , k = 0;
		cin >> x >> y >> k;
		new_line(x , y , k);
		new_line(y , x , k);
	}
	for(int i = 1;i <= m;++ i)
	{
		cin >> query.at(i);
	}
	dp.at(0) = INT_MAX;
	sum_now = n;
	get_root(1 , 0);
	dfs(root_now);
	for(int i = 1;i <= m;++ i)
	{
		if(solved.at(i))
		{
			cout << "AYE" << endl;
		}
		else
		{
			cout << "NAY" << endl;
		}
	}
	return 0;
}

2024/7/16 09:52
加载中...