【Luogu3806】点分治（点分治）

题面

题目描述

给定一棵有n个点的树

询问树上距离为k的点对是否存在。

输入格式：

n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径

接下来m行每行询问一个K

输出格式：

对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号)

题解

点分治的模板题目，不做过多的解释

据我这个蒟蒻的观察

这道题的复杂度是\(O(n^2)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 11000

#define INF 1000000000

#define K 10000000

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line

{

    int v,next,w;

}e[MAX<<1];

int h[MAX],cnt=1;

int size[MAX],minr,root,Size;

int S[MAX],tot;

bool vis[MAX];

int num[K+10],n,m;

inline void Add(int u,int v,int w)

{

    e[cnt]=(Line){v,h[u],w};

    h[u]=cnt++;

}

void Getroot(int u,int ff)

{

    size[u]=1;

    int ret=0;

    for(int i=h[u];i;i=e[i].next)

    {

        int v=e[i].v;

        if(vis[v]||v==ff)continue;

        Getroot(v,u);

        ret=max(ret,size[v]);

        size[u]+=size[v];

    }

    ret=max(ret,Size-size[u]);

    if(ret<minr)minr=ret,root=u;

}

void Getdep(int u,int ff,int dep)

{

    S[++tot]=dep;

    for(int i=h[u];i;i=e[i].next)

    {

        int v=e[i].v;

        if(v==ff||vis[v])continue;

        Getdep(v,u,dep+e[i].w);

    }

}

void Calc(int u,int fl,int pr)

{

    tot=0;

    Getdep(u,u,0);

    for(int i=1;i<=tot;++i)

        for(int j=1;j<=tot;++j)

            if(fl&&S[i]+S[j]<=K)num[S[i]+S[j]]++;

            else if(S[i]+S[j]+pr<=K)num[S[i]+S[j]+pr]--;

}

void DFS(int u)

{

    Calc(u,1,0);

    vis[u]=true;

    for(int i=h[u];i;i=e[i].next)

    {

        int v=e[i].v;

        if(vis[v])continue;

        Calc(v,0,e[i].w*2);

        minr=n;Size=size[v];Getroot(v,u);

        DFS(root);

    }

}

int main()

{

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

    for(int i=1,u,v,w;i<n;++i)

    {

        u=read(),v=read(),w=read();

        Add(u,v,w);Add(v,u,w);

    }

    minr=n;Getroot(1,1);

    DFS(root);

    while(m--)

        num[read()]?puts("AYE"):puts("NAY");

    return 0;

}