萌新求救

呜呜呜呜点分治WA了

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 4e7 + 17;
const int INF = 1e9 + 17;

struct node
{
    int v,w,next;
}e[MAXN];
int head[MAXN],q[MAXN],pre[MAXN],size[MAXN],maxx[MAXN],d[MAXN],res[MAXN],rt,n,m,tot,sum,cnt;
bool vis[MAXN];

void add(int u,int v,int w)
{
    e[++tot].v = v;
    e[tot].w = w;
    e[tot].next = head[u];
    head[u] = tot;
}

void getG(int u,int fa)
{
    size[u] = 1;
    maxx[u] = 0;
    for(int i = head[u];i;i = e[i].next)
    {
        int v = e[i].v;
        if(v == fa || vis[v])continue;
        getG(v,u);
        maxx[u] = max(maxx[u],size[v]);
        size[u] += size[v];
    }
    maxx[u] = max(maxx[u],sum - size[u]);
    if(maxx[u] < maxx[rt])rt = u;
}

void getdis(int u,int fa)
{
    int now = cnt;
    for(int i = head[u];i;i = e[i].next)
    {
        int v = e[i].v;
        int w = e[i].w;
        if(v == fa || vis[v])continue;
        d[++cnt] = d[now] + w;
        getdis(v,u);
    }
}

void dfs(int u,int fa)
{
    queue<int>tag;
    tag.push(0);
    pre[0] = 1;
    vis[u] = 1;
    for(int j = head[u];j;j = e[j].next)
    {
        int v = e[j].next;
        int w = e[j].w;
        if(v == fa || vis[v])continue;
        cnt = 0;
        d[++cnt] = w;
        getdis(v,u);
        for(int i = 1;i <= cnt;i += 1)
            for(int k = 1;k <= m;k += 1)
                if(d[i] <= q[k])res[k] |= pre[q[k] - d[i]];
        for(int i = 1;i <= cnt;i += 1)
            if(d[i] < 10000010)
            {
                if(!pre[d[i]])
                tag.push(d[i]);
                pre[d[i]] = 1;
            }
    }
    while(!tag.empty())pre[tag.front()] = 0,tag.pop();
    for(int i = head[u];i;i = e[i].next)
    {
        int v = e[i].v;
        if(v == fa || vis[v])continue;
        sum = size[v];
        rt = 0;
        maxx[0] = INF;
        getG(v,u);
        getG(rt,-1);
        dfs(rt,u);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1,u,v,w;i <= n - 1;i += 1)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i = 1;i <= m;i += 1)
        scanf("%d",&q[i]);
    rt = 0;
    maxx[0] = INF;
    sum = n;
    getG(1,-1);
    getG(rt,-1);
    dfs(rt,-1);
    for(int i = 1;i <= m;i += 1)
    {
        if(res[i])printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}