HDU 4123 树状DP+RMQ-白红宇

HDU 4123 树状DP+RMQ

阅读量：2441 次

发布时间：2019-05-10

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

/******************************************************************************************************************    尼玛。。。神题。。。居然能卡RMQ的log2的。。。解法就是先用树状DP预处理整棵树，得到每个节点距离其他节点的最大值，这个时间复杂度是O(n)，然后在得到的dp数组上做RMQ询问，注意在询问过程中，可以用一个队列维护，只要保持整个队列中极值之差<=q即可，RMQ的预处理时间复杂度为O(nlog n)，询问的时间复杂度为O(mn)，不加优化的话，TLE掉。。。然后尼玛上网查下优化居然是把RMQ的log2用数组代替掉。。。碉堡了。。。******************************************************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;//typedef long long LL; //GNU C++//typedef unsigned long long ULL;typedef __int64 LL; //Visual C++ 2010typedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef map
                                 
                                  ::iterator MI;typedef vector
                                  
                                   ::iterator VI;typedef list
                                   
                                    ::iterator LI;typedef set
                                    
                                     ::iterator SI;template 
                                     
                                      T sqa(const T &x){ return x * x;}template 
                                      
                                       T gcd(T a, T b){ if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;}template 
                                       
                                        T ext_gcd(T a, T b, T &x, T &y){ if (!b) { x = 1; y = 0; return a; } T d = ext_gcd(b, a % b, x, y); T t = x; x = y; y = t - a / b * y; return d;}template 
                                        
                                         T invmod(T a, T p){ LL inv, y; ext_gcd(a, p, inv, y); inv < 0 ? inv += p : 0; return inv;}const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 50004;int n, m;struct Edges{ int end; int len, max_len; int next;}edges[MAXN << 1];int ecnt, head[MAXN];int dp[MAXN];int bin[22], dpMI[MAXN][22], dpMX[MAXN][22];bool hs[MAXN];int lg2[MAXN];int myLog2(const int &x){ int l = 0, r = 22, mid = (l + r) >> 1; int res = 0; while (l <= r) { mid = (l + r) >> 1; if (bin[mid] <= x) { l = mid + 1; res = mid; } else { r = mid - 1; } } return res;}void preprocess(){ bin[0] = 1; for (int i = 1; i < 22; ++i) { bin[i] = bin[i - 1] << 1; } int ind = 0; for (int i = 1; i < MAXN; ++i) { if (i < bin[ind + 1]) { lg2[i] = ind; } else { lg2[i] = ++ind; } } return ;}void inline add_edge(int u, int v, int c){ edges[ecnt].end = v; edges[ecnt].len = c; edges[ecnt].max_len = 0; edges[ecnt].next = head[u]; head[u] = ecnt++; return ;}void dfs_root(const int &u){ hs[u] = true; int v, c; for (int i = head[u]; i != -1; i = edges[i].next) { v = edges[i].end; c = edges[i].len; if ( hs[v] ) { continue ; } dfs_root(v); edges[i].max_len = dp[v] + edges[i].len; dp[u] = max( dp[u], dp[v] + edges[i].len ); } return ;}void dfs_leaf(const int &t, const int &u){ if ( hs[u] ) { return ; } hs[u] = true; int v; int mx = 0; for (int i = head[t]; i != -1; i = edges[i].next) { v = edges[i].end; if (u == v) { continue ; } mx = max( mx, edges[i].max_len ); } for (int i = head[u]; i != -1; i = edges[i].next) { v = edges[i].end; if (t == v) { edges[i].max_len = edges[i].len + mx; break ; } } for (int i = head[u]; i != -1; i = edges[i].next) { dp[u] = max( dp[u], edges[i].max_len ); } for (int i = head[u]; i != -1; i = edges[i].next) { v = edges[i].end; if ( hs[v] ) { continue ; } dfs_leaf(u, v); } return ;}void initST(){ for (int i = 1; i <= n; ++i) { dpMI[i][0] = dpMX[i][0] = dp[i]; } int k = lg2[n]; for (int j = 1; j <= k; ++j) { for (int i = 1; i + bin[j] - 1 <= n; ++i) { dpMI[i][j] = min( dpMI[i][j - 1], dpMI[ i + bin[j - 1] ][j - 1] ); dpMX[i][j] = max( dpMX[i][j - 1], dpMX[ i + bin[j - 1] ][j - 1] ); } } return ;}int queryST(int l, int r){ int k = lg2[r - l + 1]; return max( dpMX[l][k], dpMX[r - bin[k] + 1][k] ) - min( dpMI[l][k], dpMI[r - bin[k] + 1][k]);}int search(const int &q){ int l = 1, r = 1; int res = 0; while (r <= n) { if (queryST(l, r) > q) { break ; } ++r; } --r; res = r - l + 1; while (r <= n) { if (queryST(l, r) <= q) { res = max(res, r - l + 1); ++r; } else { ++l; } } return res;}void ace(){ const int &root = 1; int u, v, c; int q; while (scanf("%d %d", &n, &m), n || m) { ecnt = 0; CLR(head, -1); for (int i = 0; i < n - 1; ++i) { scanf("%d %d %d", &u, &v, &c); add_edge(u, v, c); add_edge(v, u, c); } CLR(hs, false); CLR(dp, 0); dfs_root(1); CLR(hs, false); for (int i = head[root]; i != -1; i = edges[i].next) { u = edges[i].end; dfs_leaf(root, u); } initST(); while (m--) { scanf("%d", &q); printf("%d\n", search(q)); } } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif preprocess(); ace(); return 0;}