求调淀粉质

P3806 【模板】点分治 1

Debarkation @ 2022-10-19 17:53:52

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}
const int N = 1005;
const int inf = 2147483647;
int n, m, cnt, heart, maxheart, siz[N], dis[N], head[N], k, tail;
vector<int>vcnt;
bitset<N>vis;
bitset<10000001>vvis;
struct edge {
    int next, to, val;
} e[N << 1];
void add(int u, int v, int d) {
    e[++cnt] = {head[u], v, d};
    head[u] = cnt;
}
void getheart(int u, int father, int tot) {
    siz[u] = 1;
    int maxx = 0;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == father || vis[v])
            continue;
        getheart(v, u, tot);
        siz[u] += siz[v];
        maxx = max(maxx, siz[v]);
    }
    maxx = max(maxx, tot - siz[u]);
    if (maxheart > maxx) {
        maxheart = maxx ;
        heart = u;
    }
}
void getdis(int u, int father, int Dis) {
    dis[++tail] = Dis;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to, w = e[i].val;
        if (v != father && !vis[v])
            getdis(v, u, Dis + w);
    }
}
bool calc(int u, int k) {
    bool res = 0;
    vcnt.clear();
    vvis[0] = 1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to, w = e[i].val;
        if (vis[v])
            continue;
        tail = 0;
        getdis(v, u, w);
        for (int j = 1; j <= tail; j++)
            if (dis[j] <= k)
                res |= vvis[k - dis[j]];
        for (int j = 1; j <= tail; j++) {
            if (dis[j] <= k) {
                if(dis[j]==k)
                    res|=1;
                vvis[dis[j]] = 1;
                vcnt.push_back(dis[j]);
            }
        }
    }
    for (int i = 0; i < (int)vcnt.size(); i++)
        vvis[vcnt[i]] = 0;
    return res;
}
bool work(int u, int k) {
    vis[u] = 1;
    bool res = 0;
    res |= calc(u, k);
    if (res == 1)
        return 1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (vis[v])
            continue;
        maxheart = inf;
        getheart(v, 0, siz[v]);
        res |= work(heart, k);
        if (res == 1)
            return 1;
    }
    return res;
}
int main() {
    n = read();
    m = read();
    for (int i = 1; i < n; i++) {
        int x, y, z;
        x = read();
        y = read();
        z = read();
        add(x, y, z);
        add(y, x, z);
    }
    for (int i = 1; i <= m; i++) {
        cin >> k;
        maxheart = inf;
        getheart(1, 0, n);
        if (work(heart, k))
            cout << "AYE" << endl;
        else
            cout << "NAY" << endl;
    }
}

全Wa不知道错在哪了


|