学习笔记 DSU on tree(树上启发式合并)
          
            
            
            
            
              
                
              
              
                发表于
              
              
                
              
              
            
            
              
              
            
          
          
            
            
              |
            
              
                
              
              
                分类于
              
              
                算法&&学习笔记
                
                
              
            
          
          
            
          
          
          
          
          
          
        
      树上启发式合并(DSU on Tree)用于解决一类离线的、询问子树信息的问题,它拥有 $\mathcal{O} (n \log n)$ 的优秀时间复杂度,并且常数小,实现难度低。
NOI2005 月下柠檬树
          
            
            
            
            
              
                
              
              
                发表于
              
              
                
              
              
            
            
              
              
                
                |
                
                
                  
                
                
                  更新于
                
                
              
            
          
          
            
            
              |
            
              
                
              
              
                分类于
              
              
                题解
                
                
              
            
          
          
            
          
          
          
          
          
          
        
      NOI2015 品酒大会
          
            
            
            
            
              
                
              
              
                发表于
              
              
                
              
              
            
            
              
              
                
                |
                
                
                  
                
                
                  更新于
                
                
              
            
          
          
            
            
              |
            
              
                
              
              
                分类于
              
              
                题解
                
                
              
            
          
          
            
          
          
          
          
          
          
        
      Code+ #1 Yazid的新生舞会
          
            
            
            
            
              
                
              
              
                发表于
              
              
                
              
              
            
            
              
              
                
                |
                
                
                  
                
                
                  更新于
                
                
              
            
          
          
            
            
              |
            
              
                
              
              
                分类于
              
              
                题解