本文共 2925 字，大约阅读时间需要 9 分钟。

Vanya wants to minimize a tree. He can perform the following operation multiple times: choose a vertex v, and two disjoint (except for v) paths of equal length a0 = v, a1, ..., ak, and b0 = v, b1, ..., bk. Additionally, vertices a1, ..., ak, b1, ..., bk must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices b1, ..., bk can be effectively erased:

Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.

61 22 32 44 51 6

3

71 21 33 41 55 66 7

-1

题意：

给一棵树，如果两条链，像上面一样，a[i]和b[i]都没有邻居，就可以合并它们，问最后能不能合并成一条链，且要求链长度最小

题解：

从叶子节点bfs,对于每一个节点用set保存从他下方的节点到这个节点的链的长度，如果有相同长度的就会自动“合并”（set的功能）。边bfs边删边，不断取叶子结点进行向上缩。

详见代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define rep(i,a,n) for (int i=a;i
           
            =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
            
              VI;typedef long long ll;typedef pair
             
               PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=2e5+100;set
              
                g[maxn];set
               
                 d[maxn];queue
                
                  q;int vis[maxn];int re(int x){ while(x%2==0) x/=2; return x;}int solve(){ while(!q.empty()) { int u=q.front(); q.pop(); if(vis[u]) continue; if(g[u].size()==1) { if(d[u].size()==1) { int v=*g[u].begin(); if(vis[v]) continue; g[u].erase(v),g[v].erase(u); d[v].insert(*d[u].begin()+1); if(g[v].size()<=1) q.push(v); vis[u]=1; } } else if(g[u].size()==0) { if(d[u].size()>=3) return -1; else if(d[u].size()==2) return re(*d[u].begin()+*d[u].rbegin()); else return re(*d[u].begin()); } } return -1;}int main(){ int n; scanf("%d",&n); rep(i,1,n) { int u,v; scanf("%d%d",&u,&v); g[u].insert(v),g[v].insert(u); } rep(i,1,n+1) if(g[i].size()==1) q.push(i),d[i].insert(0); memset(vis,0,sizeof(vis)); printf("%d\n",solve()); return 0;}
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/fouzhe/article/details/55803093 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！