HDU 5029 Relief grain（树链剖分） - c++编程基础

题目链接~~>

做题感悟：这题真的很巧妙，分析了一下午才分析懂其中的奥妙，感觉收获很大。

解题思路：

首先需要树链剖分一下，把树剖分成链。然后的思想和HDU 5044 差不多，只不过这个不用数组遍历，而是用线段树代替数组。如果你在[ a ,b ] 区间染色，则可以让 a 节点加上这种颜色，让 b + 1 减去这种颜色，这样最后遍历一下数组就可以了，但是这题每个节点可以染许多颜色，所以不可以和数组一样只遍历一次，我们可以把那些点弄到线段树上，这样只需要在线段树上更新点就可以了，每一次得到的颜色一定是线段树根节点的颜色。

代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
  
   
#include
   
     #include
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   #include
                  
                    using namespace std ; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const INT mod = 1000000007 ; const int MY = 1400 + 5 ; const int MX = 100000 + 5 ; int n ,m ,num ,idx ,maxn ; int head[MX] ,father[MX] ,ti[MX] ,top[MX] ,dep[MX] ,siz[MX] ,son[MX] ,ans[MX] ,P[MX] ; struct Edge // 邻接表 { int v ,next ; }E[MX*2] ; struct NODE { int u ,v ,w ; NODE(){} ; NODE(int _u ,int _v ,int _w):u(_u) ,v(_v) ,w(_w){} ; } ; vector
                   
                    St ; vector
                    
                     G[MX] ; void addedge(int u ,int v) { E[num].v = v ; E[num].next = head[u] ; head[u] = num++ ; E[num].v = u ; E[num].next = head[v] ; head[v] = num++ ; } void dfs_find(int u ,int fa) { dep[u] = dep[fa] + 1 ; siz[u] = 1 ; son[u] = 0 ; father[u] = fa ; for(int i = head[u] ; i != -1 ;i = E[i].next) { int v = E[i].v ; if(v == fa) continue ; dfs_find(v ,u) ; siz[u] += siz[v] ; if(siz[son[u]] < siz[v]) son[u] = v ; } } void dfs_time(int u ,int fa) { ti[u] = idx++ ; top[u] = fa ; if(son[u]) dfs_time(son[u] ,top[u]) ; for(int i = head[u] ;i != -1 ; i = E[i].next) { int v = E[i].v ; if(v == father[u] || v == son[u]) continue ; dfs_time(v ,v) ; } } void LCA(int u ,int v ,int w) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u ,v) ; St.push_back(NODE(ti[top[u]] ,ti[u]+1 ,w)) ; u = father[top[u]] ; } if(dep[u] > dep[v]) swap(u ,v) ; St.push_back(NODE(ti[u] ,ti[v]+1 ,w)) ; } struct node { int le ,rt ,num ,type ; }T[MX*4] ; void build(int x ,int le ,int rt) // 建树 { T[x].num = 0 ; T[x].le = le ; T[x].rt = rt ; if(le == rt) { T[x].type = le ; return ; } int Mid = (le + rt)>>1 ; build(L(x) ,le ,Mid) ; build(R(x) ,Mid+1 ,rt) ; } void push_up(int x) { T[x].num = max(T[L(x)].num ,T[R(x)].num) ; if(T[L(x)].num >= T[R(x)].num) T[x].type = T[L(x)].type ; else T[x].type = T[R(x)].type ; } void update(int x ,int pos ,int add) { if(T[x].le == T[x].rt) { T[x].num += add ; return ; } int Mid = (T[x].le + T[x].rt)>>1 ; if(pos <= Mid) update(L(x) ,pos ,add) ; else update(R(x) ,pos ,add) ; push_up(x) ; } void init() { num = 0 ; memset(head ,-1 ,sizeof(head)) ; memset(ans ,0 ,sizeof(ans)) ; memset(P ,0 ,sizeof(P)) ; St.clear() ; for(int i = 0 ;i <= n+1 ; ++i) G[i].clear() ; } int main() { //freopen("input.txt" ,"r" ,stdin) ; int u ,v ,w ; while(scanf("%d%d" ,&n ,&m) ,n+m) { init() ; for(int i = 1 ;i < n ; ++i) { scanf("%d%d" ,&u ,&v) ; addedge(u ,v) ; } // 树链剖分 dep[1] = siz[0] = 0 ; dfs_find(1 ,1) ; idx = 1 ; dfs_time(1 ,1) ; maxn = 1 ; for(int i = 1 ;i <= n ; ++i) // 转换节点编号 P[ti[i]] = i ; for(int i = 0 ;i < m ; ++i) // 处理询问 { scanf("%d%d%d" ,&u ,&v ,&w) ; LCA(u ,v ,w) ; maxn = max(w ,maxn) ; } build(1 ,1 ,maxn) ; // 建树 int Size = St.size() ; for(int i = 0 ;i < Size ; ++i) // 处理 { int u = St[i].u ,v = St[i].v ,w = St[i].w ; G[u].push_back(w) ; G[v].push_back(-w) ; } for(int i = 1 ;i <= n ; ++i) // 利用前缀思想依次遍历每个节点 ,在线段树中的节点 { sort(G[i].begin() ,G[i].end()) ; for(int j = 0 ;j < (int)G[i].size() ; ++j) // 插入每个节点 { int color = G[i][j] ; if(color < 0) update(1 ,-color ,-1) ; else update(1 ,color ,1) ; } if(T[1].num) ans[P[i]] = T[1].type ; else ans[P[i]] = 0 ; } for(int i = 1 ;i <= n ; ++i) printf("%d\n" ,ans[i]) ; } return 0 ; }