洛谷 P3806 点分治模板

题目：https://www.luogu.org/problemnew/show/P3806

就是点分治~

每次暴力枚举询问即可，复杂度是 nmlogn；

注意 tmp[0]=1 ！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=,maxm=1e7+,inf=0x3f3f3f3f;

int n,m,hd[maxn],ct,to[maxn<<],nxt[maxn<<],w[maxn<<],dis[maxn],siz[maxn];

int mx,rt,sum,q[],tmp[maxm],sta[maxn],top,f[maxn];

bool vis[maxn],ans[];

void add(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; w[ct]=z; hd[x]=ct;}

void getrt(int x,int fa)

{

    siz[x]=; int nmx=;

    for(int i=hd[x],u;i;i=nxt[i])

    {

        if((u=to[i])==fa||vis[u])continue;

        getrt(u,x); siz[x]+=siz[u];

        nmx=max(nmx,siz[u]);

    }

    nmx=max(nmx,sum-siz[x]);

    if(nmx<mx)mx=nmx,rt=x;

}

void dfs(int x,int fa)

{

    for(int i=hd[x],u;i;i=nxt[i])

    {

        if((u=to[i])==fa||vis[u])continue;

        dis[u]=dis[x]+w[i];

        for(int j=;j<=m;j++)

            if(dis[u]<=q[j]&&!ans[j])

            {

                ans[j]=tmp[q[j]-dis[u]];

                sta[++top]=dis[u];

            }

        dfs(u,x);

    }

}

void work(int x,int ss)

{

    vis[x]=; int p=;

    for(int i=hd[x],u;i;i=nxt[i])

    {

        if(vis[u=to[i]])continue;

        dis[u]=w[i];

        for(int j=;j<=m;j++)

            if(dis[u]<=q[j]&&!ans[j])

            {

                ans[j]=tmp[q[j]-dis[u]];

                sta[++top]=dis[u];

            }

        dfs(u,x);

        for(;p<=top;p++)tmp[sta[p]]++;

    }

    for(int i=;i<=top;i++)tmp[sta[i]]--; top=;

    for(int i=hd[x],u;i;i=nxt[i])

    {

        if(vis[u=to[i]])continue;

        sum=(siz[u]>siz[x]?ss-siz[x]:siz[u]); mx=inf;

        getrt(u,); work(u,sum);

    }

}

int main()

{

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

    for(int i=,x,y,z;i<n;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z); add(y,x,z);

    }

    for(int i=;i<=m;i++)scanf("%d",&q[i]);

    tmp[]=;//!

    sum=n; mx=inf; getrt(,);

    work(rt,sum);

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

        if(ans[i])printf("AYE\n");

        else printf("NAY\n");

    return ;

}