[P3806] 【模板】点分治

辣鸡蒟蒻怎么今天才来敲这个模板题

好像还敲了很久的样子

（大雾）
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 10005;

vector<pair<int,int> > g[N];

int dis[N],siz[N],msiz[N],n,m,k[N],ans[N],u[N];

vector <int> st;

int buc[10000005];

vector <int> bl;

vector <int> wl;

void buc_push(int x) {

    if(x>1e+7) return;

    buc[x]=1;

    bl.push_back(x);

}

int buc_query(int x) {

    if(x<0 || x>1e+7) return 0;

    return buc[x];

}

void buc_clear() {

    for(int i=0;i<bl.size();i++)

        buc[bl[i]]=0;

    bl.clear();

}

void dfs1(int p,int from) {

    siz[p]=1;

    msiz[p]=0;

    st.push_back(p);

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i].first, w=g[p][i].second;

        if(q!=from && u[q]==0) {

            dfs1(q,p);

            siz[p]+=siz[q];

            msiz[p]=max(msiz[p],siz[q]);

        }

    }

}

void dfs2(int p,int from) {

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i].first, w=g[p][i].second;

        if(q!=from && u[q]==0) {

            dis[q]=dis[p]+w;

            dfs2(q,p);

        }

    }

}

void dfs3(int p,int from) {

    for(int i=1;i<=m;i++) {

        if(buc_query(k[i]-dis[p])) ans[i]=1;

    }

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i].first, w=g[p][i].second;

        if(q!=from && u[q]==0) {

            dfs3(q,p);

        }

    }

    wl.push_back(dis[p]);

}

int findroot(int p) {

    st.clear();

    dfs1(p,0);

    int r=0,rv=1e+9;

    for(int i=0;i<st.size();i++) {

        msiz[st[i]]=max(msiz[st[i]],siz[p]-siz[st[i]]);

        if(msiz[st[i]]<rv) r=st[i],rv=msiz[st[i]];

    }

    return r;

}

void calc(int p) {

    dis[p]=0;

    dfs2(p,0);

    buc_clear();

    buc_push(0);

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i].first, w=g[p][i].second;

        if(u[q]==0) {

            dfs3(q,0);

            for(int j=0;j<wl.size();j++) {

                buc_push(wl[j]);

            }

            wl.clear();

        }

    }

}

void solve(int p) {

    int r=findroot(p);

    u[r]=1;

    calc(r);

    for(int i=0;i<g[r].size();i++) {

        int q=g[r][i].first, w=g[r][i].second;

        if(u[q]==0) {

            solve(q);

        }

    }

}

signed main() {

    scanf("%lld%lld",&n,&m);

    for(int i=1;i<n;i++) {

        int t1,t2,t3;

        scanf("%lld%lld%lld",&t1,&t2,&t3);

        g[t1].push_back(make_pair(t2,t3));

        g[t2].push_back(make_pair(t1,t3));

    }

    for(int i=1;i<=m;i++) scanf("%lld",&k[i]);

    solve(1);

    for(int i=1;i<=m;i++) {

        cout<<(ans[i]?"AYE":"NAY")<<endl;

    }

}
巴特西

[P3806] 【模板】点分治 - 点分治

最新文章

热门文章
