description

求树上长度为\(k\)的路径是否存在。

data range

\[n\le 10000,k\le 10000000\]

solution

点分治复习。。。

使用普通的点分治枚举路径模板即可。

一个小细节

本人初学点分治的时候是这样写的

int sum,rt,sz[N],w[N];bool vis[N];void getrt(int u,int ff){//找到对应连通块的重心  sz[u]=1;w[u]=0;  for(RG int i=head[u];i;i=nxt[i]){    RG int v=to[i];if(v==ff||vis[v])continue;    getrt(v,u);sz[u]+=sz[v];    w[u]=max(w[u],sz[v]);  }  w[u]=max(w[u],blk-sz[u]);  if(w[rt]>w[u])rt=u;}void solve(int u){//递归分治  vis[u]=1;  for(RG int i=head[u];i;i=nxt[i]){    RG int v=to[i];if(vis[v])continue;    rt=0;blk=sz[v];    getrt(v,0);    solve(rt);  }}int main(){    //...    rt=0;w[0]=sum=n;    getrt(1,0);    solve(rt);    return 0;}

现在感觉这样写有问题。

关键出在直接赋值\(sum=sz[v]\)上。

给出一棵树:

我们第一次选择的重心是节点\(3\)

然而这时\(sz[1]=6\)

于是我们递归解决上面部分的时候重心就会受到影响

然后就可能会\(T\)

解决方法是两边\(dfs\)像这样似乎常数又加大了:

int sum,rt,sz[N],w[N];bool vis[N];void getrt(int u,int ff){//找到对应连通块的重心  sz[u]=1;w[u]=0;  for(RG int i=head[u];i;i=nxt[i]){    RG int v=to[i];if(v==ff||vis[v])continue;    getrt(v,u);sz[u]+=sz[v];    w[u]=max(w[u],sz[v]);  }  w[u]=max(w[u],blk-sz[u]);  if(w[rt]>w[u])rt=u;}void solve(int u){//递归分治  vis[u]=1;  for(RG int i=head[u];i;i=nxt[i]){    RG int v=to[i];if(vis[v])continue;    rt=0;blk=sz[v];    getrt(v,0);    getrt(rt,0);//第二遍dfs    solve(rt);  }}int main(){    //...    rt=0;w[0]=sum=n;    getrt(1,0);    getrt(rt,0);//第二遍dfs    solve(rt);    return 0;}

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include