#8#9tle了?

P3806 【模板】点分治 1

shitbro @ 2021-02-02 21:49:11

#include <bits/stdc++.h>
#define debug cout<<"YES"<<endl;
using namespace std;
const int N = 1e4 + 5,INF = 1e9 + 5;
queue <int> tag;

int n,m,sum,MAX,root,cnt,tot;

int siz[N],dis[N],q[N],dd[N],head[N];

bool judge[100000005],res[N],vis[N];

struct edge {
    int to,nxt,val;
}e[N << 1];
void add_edge(int u,int v,int w) {
    e[++ tot].nxt = head[u];
    e[tot].to = v;
    e[tot].val = w;
    head[u] = tot;
    e[++ tot].nxt = head[v];
    e[tot].to = u;
    e[tot].val = w;
    head[v] = tot;
}
void getsize(int u,int fa) {
    siz[u] = 1;
    int maxl = 0;
    for(int i = head[u];i;i = e[i].nxt) {   
        int v = e[i].to;
        if(v == fa || vis[v]) continue;
        getsize(v,u);
        siz[u] += siz[v];
        maxl = max(maxl,siz[u]);
    }
    maxl = max(maxl,sum - siz[u]);
    if(maxl < MAX) {
        MAX = maxl;
        root = u;
    }
}
void getdis(int u,int fa) {
    dd[++ cnt] = dis[u];
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa || vis[v]) continue;
        dis[v] = dis[u] + e[i].val;
        getdis(v,u);
    }
}
void dfs(int u,int fa) {
    judge[0] = 1;
    tag.push(0);
    vis[u] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa || vis[v]) continue;
        dis[v] = e[i].val;
        getdis(v,u);
        for(int j = 1;j <= cnt;j ++) {
            for(int k = 1;k <= m;k ++) {
                if(q[k] - dd[j] >= 0) {
                    res[k] |= judge[q[k] - dd[j]];
                }
            }
        }
        for(int j = 1;j <= cnt;j ++) {
            tag.push(dd[j]);
            judge[dd[j]] = 1;
        }
        cnt = 0;
    }
    while(!tag.empty()) {
        judge[tag.front()] = 0;
        tag.pop();
    }
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa || vis[v]) continue;
        sum = siz[v];
        root = 0;
        MAX = INF;
        getsize(v,u);
        getsize(root,0);
        dfs(root,u);
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1;i < n;i ++) {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }
    for(int i = 1;i <= m;i ++) {
        scanf("%d",&q[i]);
    }
    root = 0;
    MAX = INF;
    sum = n;
    getsize(1,0);
    getsize(root,0);
    dfs(root,0);
    for(int i = 1;i <= m;i ++) {
        if(res[i]) puts("AYE");
        else puts("NAY");
    }
    return 0;
}

|