救救我WA 4&&6 求助
查看原帖
救救我WA 4&&6 求助
661164
Zkl21楼主2023/6/7 22:06
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = N << 1, S = 1e7 + 10;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int q[N], p[N], k[110];
bool f[S], ans[110];
void add(int a, int b, int c)
{
    e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}
int get_size(int u, int fa)
{
    if (st[u])
        return 0;
    int res = 1;
    for (int i = h[u], j = e[i]; i; i = ne[i], j = e[i])
        if (j != fa)
            res += get_size(j, u);
    return res;
}
int get_wc(int u, int fa, int tot, int &wc)
{
    if (st[u])
        return 0;
    int sum = 1, ms = 0;
    for (int i = h[u], j = e[i]; i; i = ne[i], j = e[i])
        if (j != fa)
        {
            int t = get_wc(j, u, tot, wc);
            ms = max(ms, t);
            sum += t;
        }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2)
        wc = u;
    return sum;
}
void get_dist(int u, int fa, int dist, int &qt)
{
    if (st[u])
        return;
    q[qt++] = dist;
    for (int i = h[u], j = e[i]; i; i = ne[i], j = e[i])
        if (j != fa)
            get_dist(j, u, dist + w[i], qt);
}
void calc(int u)
{
    if (st[u])
        return;
    get_wc(u, -1, get_size(u, -1), u); // 找重心
    st[u] = 1;
    int pt = 0;
    f[0] = 1;
    for (int i = h[u], j = e[i]; i; i = ne[i], j = e[i])
    {
        int qt = 0;
        get_dist(j, u, w[i], qt);
        for (int l = 0; l < qt; l++)
        {
            auto t = q[l];
            if (t > 1e7)
                continue;
            p[pt++] = t;
            f[t] = 1;
        }
    }
    for (int i = 1; i <= m; i++)
        if (!ans[i])
        {
            if (f[k[i]])
            {
                ans[i] = 1;
                continue;
            }
            for (int j = 0; j < pt; j++)
                if (k[i] >= p[j] && p[j] * 2 != k[i] && f[k[i] - p[j]])
                {
                    ans[i] = 1;
                    break;
                }
        }
    for (int i = 0; i < pt; i++)
        if (p[i] <= 1e7)
            f[p[i]] = 0;
    for (int i = h[u], j = e[i]; i; i = ne[i], j = e[i])
        calc(j);
}
int main()
{
#ifndef Luogu // 记得删'n'
    freopen("E:\\in and out\\in.in", "r", stdin);
    freopen("E:\\in and out\\out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for (int i = 1; i <= m; i++)
        cin >> k[i];
    calc(1);
    for (int i = 1; i <= m; i++)
        puts(ans[i] ? "AYE" : "NAY");
    return 0;
}
2023/6/7 22:06
加载中...