洛谷P3806 【模板】点分治1

题目描述

给定一棵有n个点的树

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

AYE

说明

对于30%的数据n<=100

对于60%的数据n<=1000,m<=50

对于100%的数据n<=10000,m<=100,c<=1000,K<=10000000

题解

　　看一看$k$的范围，可以直接把所有答案预处理出来，然后$O(1)$查询

　　时间复杂度$O(n^2)$，随机数据可以跑

　　据说还有$O(nlog^2n)$的方法，然而我不会……

 //minamoto

 #include<cstdio>

 #include<iostream>

 #define inf 0x3f3f3f3f

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;

 int ans[];

 int ver[N<<],head[N],Next[N<<],edge[N<<];

 int sz[N],son[N],st[N];bool vis[N];

 int n,m,size,mx,rt,tot,top;

 inline void add(int u,int v,int e){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e;

     ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=e;

 }

 void getrt(int u,int fa){

     sz[u]=,son[u]=;

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

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

         getrt(v,u);

         sz[u]+=sz[v],cmax(son[u],sz[v]);

     }

     cmax(son[u],size-sz[u]);

     if(son[u]<mx) mx=son[u],rt=u;

 }

 void query(int u,int fa,int d){

     st[++top]=d;

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

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

         query(v,u,d+edge[i]);

     }

 }

 void solve(int rt,int d,int f){

     top=;

     query(rt,,d);

     if(f){

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

         for(int j=i+;j<=top;++j)

         ++ans[st[i]+st[j]];

     }

     else{

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

         for(int j=i+;j<=top;++j)

         --ans[st[i]+st[j]];

     }

 }

 void divide(int u){

     vis[u]=true;

     solve(u,,);

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

         if(vis[v]) continue;

         solve(v,edge[i],);

         mx=inf,rt=,size=sz[v];

         getrt(v,);

         divide(rt);

     }

 }

 int main(){

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

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

         int u=read(),v=read(),e=read();

         add(u,v,e);

     }

     rt=,mx=inf,size=n;

     getrt(,),divide(rt);

     while(m--){

         int k=read();

         puts(ans[k]?"AYE":"NAY");

     }

     return ;

 }

巴特西

洛谷P3806 【模板】点分治1

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章