【Luogu】P3806点分治模板（点分治）

　　题目链接

　　wc听不懂lca讲的高等数学专场（一个字都听不懂），然后就自学了点分治。

　　点分治就是我先处理完跟根有关的东西，然后把根标记掉，把原树拆成若干个联通块，然后分别对每个联通块（每个小树）搞一模一样的操作。

　　然后要每次求重心，因为点分治复杂度跟递归深度有关。

　　本题判断的时候偷懒用map，其实自己写的splay也快不到哪里去的样子。qwq。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<map>

#define maxn 200020

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

struct Edge{

    int next,to,val;

}edge[maxn*];

int head[maxn],num;

inline void add(int from,int to,int val){

    edge[++num]=(Edge){head[from],to,val};

    head[from]=num;

}

map<int,bool>ext;

bool tag[maxn];

int size[maxn];

int mxn[maxn];

int stack[maxn],top;

int d[maxn];

int w[maxn];

int root=;

void getroot(int x,int fa,int lim){

    int ret=;size[x]=;

    for(int i=head[x];i;i=edge[i].next){

        int to=edge[i].to;

        if(to==fa||tag[to])    continue;

        getroot(to,x,lim);

        size[x]+=size[to];

        if(ret<size[to])    ret=size[to];

    }

    if(ret<lim-size[x])    ret=lim-size[x];

    mxn[x]=ret;

    if(ret<mxn[root]||root==)    root=x;

}

void depfind(int x,int fa,int dst){

    stack[++top]=dst;

    for(int i=head[x];i;i=edge[i].next){

        int to=edge[i].to;

        if(to==fa||tag[to])    continue;

        depfind(to,x,dst+edge[i].val);

    }

    return;

}

int getsize(int x,int fa){

    int ans=;

    for(int i=head[x];i;i=edge[i].next){

        int to=edge[i].to;

        if(to==fa||tag[to])    continue;

        ans+=getsize(to,x);

    }

    return ans;

}

void dfs(int x,int lim,int m){

    root=;

    getroot(x,x,lim);

    tag[root]=;

    ext.clear();ext[]=;

    for(int i=head[root];i;i=edge[i].next){

        int to=edge[i].to;

        if(tag[to])    continue;

        top=;

        depfind(to,to,edge[i].val);

        sort(stack+,stack+top+);

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

            if(w[j])    continue;

            for(int k=;k<=top;++k){

                int now=d[j]-stack[k];

                if(ext[now]==)    w[j]=;

            }

        }

        for(int j=;j<=top;++j)    ext[stack[j]]=;

    }

    int now=root;

    for(int i=head[now];i;i=edge[i].next){

        int to=edge[i].to;

        if(tag[to])    continue;

        int ret=getsize(to,to);

        dfs(to,ret,m);

    }

}

int main(){

    int n=read(),m=read();

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

        int x=read(),y=read(),z=read();

        add(x,y,z);

        add(y,x,z);

    }

    for(int i=;i<=m;++i)    d[i]=read();

    dfs(,n,m);

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

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

        else        printf("NAY\n");

    return ;

}

/*

13 10

1 2 1

1 4 2

4 3 5

4 5 11

5 6 4

5 7 2

4 8 7

1 10 2

9 10 9

1 11 4

11 13 5

11 12 6

12

11

10

9

8

22

13

14

15

18

*/