试题分析

其实就是一个十分暴力的算法，每次找到树的重心以后把它当为根然后再重新进行

这道题所到达长度为$k$的道路有$2$种情况

一种情况是经过根$root$,$x$到$y$的距离为$dis[x]+dis[y](lca(x,y)=root)$

而还有一种是经过子树的，就去进行分治即可

然后就没有了

如果是暴力方法的时间复杂度为：$O(floor \times n)$ $floor$为树的层数

如果是点分治的话，因为每次是树的重心所以层数不超过$\log n$,所以时间复杂度为:$O(n\log n)$

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int f=1,ans=0;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}    return f*ans;}const int MAXN=10001;const int MAXN1=10000001;int n,q;struct node{    int u,v,w,nex;}x[MAXN<<1];int cnt,head[MAXN],vis[MAXN],root,sum[MAXN],maxnson[MAXN],sigma,maxn=INT_MAX,query[MAXN],rem[MAXN];void add(int u,int v,int w){    x[cnt].u=u,x[cnt].v=v,x[cnt].w=w,x[cnt].nex=head[u],head[u]=cnt++;}void get(int xx,int fath){    sum[xx]=1;    for(int i=head[xx];i!=-1;i=x[i].nex){        if(x[i].v==fath) continue;        if(vis[x[i].v]) continue;        get(x[i].v,xx);        maxnson[xx]=max(maxnson[xx],maxnson[x[i].v]);        sum[xx]+=sum[x[i].v];    }    int pd=max(maxnson[xx],sigma-sum[xx]);    if(pd
           
            =rem[z]) pd[j]|=num_dis[query[j]-rem[z]]; for(int j=1;j<=rem[0];j++) que[++que[0]]=rem[j],num_dis[rem[j]]=1; } for(int i=1;i<=que[0];i++) num_dis[que[i]]=0;}void solve(int xx,int fath){ vis[xx]=1,num_dis[0]=1;calc(xx,fath); for(int i=head[xx];i!=-1;i=x[i].nex){ if(x[i].v==fath) continue; if(vis[x[i].v]) continue; sigma--; get(x[i].v,xx); solve(x[i].v,xx); }}int main(){ memset(head,-1,sizeof(head)); n=read(),q=read(); for(int i=1;i