题目背景

感谢hzwer的点分治互测。

题目描述

给定一棵有n个点的树

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

2 1

1 2 2

2

输出样例#1：

AYE

说明

对于30%的数据n<=100

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

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

题解

还是有点裸的点分治模板题

有趣的一点是：其实calc里跑 \(O(n^2)\) 的暴力记录哪些值可以达到，这可以过（数据水还是复杂度玄学？）

如果一定要理论复杂度正确，那就不 \(n^2\) ，每次遍历每一个询问，两次twopoints求小于等于 \(q[i]\) 的有多少对，小于等于 \(q[i]-1\) 的有多少对，相减就是等于 \(q[i]\) 的对数了

两个程序我都写了， calc里 \(n^2\) 最慢的要200多ms，\(mlogn\)的最慢只要30ms，毕竟复杂度摆在那里

两份代码都贴上来

这是暴力一点的

#include
    
     #define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long longconst int MAXN=10000+10,MAXK=10000000+10,inf=0x3f3f3f3f;int ans[MAXK],n,m,e,to[MAXN<<1],nex[MAXN<<1],beg[MAXN],w[MAXN<<1],root,f[MAXN],d[MAXN],deep[MAXN],cnt,size[MAXN],Msonsize[MAXN],finish[MAXN];template
     
       inline void read(T &x){    T data=0,w=1;    char ch=0;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')w=-1,ch=getchar();    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();    x=data*w;}template
      
        inline void write(T x,char ch='\0'){    if(x<0)putchar('-'),x=-x;    if(x>9)write(x/10);    putchar(x%10+'0');    if(ch!='\0')putchar(ch);}template
       
         inline void chkmin(T &x,T y){x=(y
        
         
           inline void chkmax(T &x,T y){x=(y>x?y:x);}template
          
            inline T min(T x,T y){return x
           
            
              inline T max(T x,T y){return x>y?x:y;}inline void insert(int x,int y,int z){ to[++e]=y; nex[e]=beg[x]; beg[x]=e; w[e]=z;}inline void getroot(int x,int f,int ntotal){ Msonsize[x]=0;size[x]=1; for(register int i=beg[x];i;i=nex[i]) if(to[i]==f||finish[to[i]])continue; else { getroot(to[i],x,ntotal); size[x]+=size[to[i]]; chkmax(Msonsize[x],size[to[i]]); } chkmax(Msonsize[x],ntotal-size[x]); if(Msonsize[x]
            
           
          
         
        
       
      
     
    

这是优秀的（ShichengXiao OrzOrzOrzOrz）

#include
    
     #define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long longconst int MAXN=10000+10,MAXM=100+10,MAXK=10000000+10,inf=0x3f3f3f3f;int n,m,e,to[MAXN<<1],nex[MAXN<<1],beg[MAXN],w[MAXN<<1],root,f[MAXN],d[MAXN],deep[MAXN],cnt,size[MAXN],Msonsize[MAXN],finish[MAXN],q[MAXM],ans[MAXM];template
     
       inline void read(T &x){    T data=0,w=1;    char ch=0;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')w=-1,ch=getchar();    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();    x=data*w;}template
      
        inline void write(T x,char ch='\0'){    if(x<0)putchar('-'),x=-x;    if(x>9)write(x/10);    putchar(x%10+'0');    if(ch!='\0')putchar(ch);}template
       
         inline void chkmin(T &x,T y){x=(y
        
         
           inline void chkmax(T &x,T y){x=(y>x?y:x);}template
          
            inline T min(T x,T y){return x
           
            
              inline T max(T x,T y){return x>y?x:y;}inline void insert(int x,int y,int z){ to[++e]=y; nex[e]=beg[x]; beg[x]=e; w[e]=z;}inline void getroot(int x,int f,int ntotal){ Msonsize[x]=0;size[x]=1; for(register int i=beg[x];i;i=nex[i]) if(to[i]==f||finish[to[i]])continue; else { getroot(to[i],x,ntotal); size[x]+=size[to[i]]; chkmax(Msonsize[x],size[to[i]]); } chkmax(Msonsize[x],ntotal-size[x]); if(Msonsize[x]