样例没过求调
查看原帖
样例没过求调
503792
Svemit楼主2023/2/3 13:29
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long ull;
const int N = 1e5 + 5, M = 1e7 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int n, m, k;
int q[N], p[N];
int ans[M];
bool st[N];
struct edge
{
	int v, w;
	edge(int v = 0, int w = 0):v(v), w(w){};
};
vector<edge> e[N];

int get_siz(int u, int fa)
{
	if(st[u]) return 0;
	int siz = 1;
	for(auto i:e[u])
	{
		int v = i.v;
		if(v == fa) continue;
		siz += get_siz(v, u);
	}
	return siz;
}

int get_root(int u, int fa, int tot, int &rt)
{
	if(st[u]) return 0;
	int siz = 1, ms = 0;
	for(auto i:e[u])
	{
		int v = i.v;
		if(v == fa) continue;
		int t = get_root(v, u, tot, rt);
		ms = max(ms, t);
		siz += t;
	}
	ms = max(ms, tot - siz);
	if(ms <= tot / 2) rt = u;
	return siz;
}

void get_dis(int u, int fa, int dis, int &qt)
{
	if(st[u] || dis > 1e7) return;
	q[++ qt] = dis;
	for(auto i:e[u])
	{
		int v = i.v, w = i.w;
		if(v == fa) continue;
		get_dis(v, u, dis + w, qt);
	}
}

void solve(int d[], int len, int f)
{
	cout << len <<endl;
	for(int i = 1;i <= len;i ++)
		for(int j = 1;j <= len;j ++)
			if(i != j && d[i] + d[j] <= 1e7)
			{
				ans[d[i] + d[j]] += f;
			}
}

void calc(int u)
{
	if(st[u]) return;
	st[u] = true;
	get_root(u, 0, get_siz(u, 0), u);
	int pt = 0;
	for(auto i:e[u])
	{
		int v = i.v, w = i.w;
		int qt = 0;
		get_dis(v, u, w, qt);
		solve(q, qt, -1);
		for(int i = 1;i <= qt;i ++)
			p[++ pt] = q[i];
	}
	solve(p, pt, 1);
	for(auto i:e[u])
	{
		int v = i.v;
		calc(v);
	}
}

int main()              //主函数
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1;i < n;i ++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back(edge(v, w));
		e[v].push_back(edge(u, w));
	}
	calc(1);
	while(m --)
	{
		int k;
		cin >> k;
		if(ans[k]) cout << "AYE\n";
		else cout << "NYA\n";
	}
    return 0;
}
2023/2/3 13:29
加载中...