UVa 1674 : Lightning Energy Report

問題リンク : http://uva.onlinejudge.org/external/16/1674.pdf

問題概要：
N個のノードからなる木が与えられる
各ノードは0からN-1まで番号が付けられている
Q個のクエリーが与えられる
クエリは次の形式で与えられる
a b c
これは、aからbまでの経路に属するノードに重みをc加算することを表す
初期は各ノードの重みは０である
全てのクエリーを処理した後の各ノードの重みを出力せよ

解法 :
Heavy Light Decompositionで木を分解して遅延評価付きRMQで処理した
これについてそれ以上かくことはない

もっと簡単な解法があるらしい

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int MAX_V = 50010;
const int IINF = INT_MAX;

struct Edge { int to,weight,index; };

int V;
vector<Edge> G[MAX_V];
vector<int> costs;

typedef pair<int,int> ii;

//RMQ LCA ------------------------------- begin
class LCA_RMQ{
private:
  int limit,N;
  vector<ii> dat;
public:
  void init(int n_){
    N = n_;
    dat.clear();
    limit = 1;
    while(limit<n_)limit*=2;
    dat.resize(2*limit);
    for(int i=0;i<2*limit-1;i++) dat[i] = ii(IINF,IINF);//ii(depth,index)
  }

  ii _build(int cur,int L,int R,const vector<ii> &buf){
    if( !( 0 <= cur && cur < 2*limit ) ) return ii(IINF,IINF);
    if( L == R-1 ) {
      if( L >= N ) return ii(IINF,IINF);
      dat[cur] = buf[L];
    } else {
      ii vl = _build(cur*2+1,L,(L+R)/2,buf);
      ii vr = _build(cur*2+2,(L+R)/2,R,buf);
      dat[cur] = min(vl,vr);
    }
    return dat[cur];
  }

  void build(const vector<ii> &buf){ _build(0,0,limit,buf); };
 
  // k番めの値(0-indexed)をaに変更
  void update(int k,ii a){
    k += limit-1;
    dat[k] = a;
    while(k > 0){
      k = (k-1)/2;
      dat[k] = (dat[k*2+1].first>dat[k*2+2].first?dat[k*2+2]:dat[k*2+1]);
    }
  }
 
  ii _query(int a,int b,int k,int l,int r){
    if(r<=a || b<=l)return ii(IINF,-1);
    else if(a<=l && r<=b)return dat[k];
     
    ii vl = _query(a,b,k*2+1,l,(l+r)/2);
    ii vr = _query(a,b,k*2+2,(l+r)/2,r);

    return min(vl,vr);
  }

  ii query(int a,int b){ return _query(a,b,0,0,limit); }
};

int root;
vector<int> id,vs,depth;


void LCA_dfs(int v,int p,int d,int &k){
  id[v] = k;
  vs[k] = v;
  depth[k++] = d;
  for(int i=0;i<(int)G[v].size();i++){
    if(G[v][i].to != p){
      LCA_dfs(G[v][i].to,v,d+1,k);
      vs[k] = v;
      depth[k++] = d;
    }
  }
}

void LCA_init(int V,LCA_RMQ &rmq){
  root = 0;
  vs.clear();
  vs.resize(V*2,0);
  depth.clear();
  depth.resize(V*2,0);
  id.clear();
  id.resize(V);
  int k = 0;
  LCA_dfs(root,-1,0,k);
  rmq.init(k+1);  
  vector<ii> tmp;
  rep(i,k) tmp.push_back(ii(depth[i],vs[i]));
  rmq.build(tmp);
}

int lca(int u,int v,LCA_RMQ &rmq){ return rmq.query(min(id[u],id[v]),max(id[u],id[v])+1).second; }

//RMQ LCA ------------------------------- end
const char EMPTY = 'X';
 
struct Node{
  int value;
  /*
    lazy : 
    A : 加算の遅延 ( ADD )
    S : 区間の要素を指定した値にする遅延 ( SET )

    lazy_coef : 
    区間にいくら加算するのかor何をセットするのかを記録
  */
  char lazy;
  int lazy_coef; 
  Node(int value=0,char lazy=EMPTY,int lazy_coef=0):value(value),lazy(lazy),lazy_coef(lazy_coef){}
};
 
class RMQ{
public:
  vector<Node> dat;
  int limit,N; // N は要素数
 
  void init(int tmp){
    N = tmp;
    int N_N = 1;
    while(N_N < N)N_N *= 2;
    limit = N_N;
    dat.resize(3*limit);
    rep(i,3*limit-1) dat[i] = Node();
  }

  int _build(int cur,int L,int R,const vector<int> &buf){
    if( !( 0 <= cur && cur < 2*limit-1 ) ) return 0;
    if( L == R-1 ){
      if( L >= N ) return 0;
      dat[cur].value = buf[L];
    } else {
      int vl = _build(cur*2+1,L,(L+R)/2,buf);
      int vr = _build(cur*2+2,(L+R)/2,R,buf);
      dat[cur].value = vl + vr;
    }
    return dat[cur].value;
  }

  void build(const vector<int> &buf) { _build(0,0,limit,buf); }

  inline void value_evaluate(int index,int L,int R){
    if( dat[index].lazy == 'A' ) dat[index].value += ( R - L ) * dat[index].lazy_coef;
    else if( dat[index].lazy == 'S' ) dat[index].value = ( R - L ) * dat[index].lazy_coef;
  }
   
  inline void lazy_evaluate(int index,int L,int R){
    value_evaluate(index,L,R);
    if( index < limit && dat[index].lazy != EMPTY ) {
      if( dat[index].lazy == 'A' ) {
        if( dat[index*2+1].lazy == EMPTY ) dat[index*2+1].lazy = 'A'; 
        if( dat[index*2+2].lazy == EMPTY ) dat[index*2+2].lazy = 'A';
        dat[index*2+1].lazy_coef += dat[index].lazy_coef;
        dat[index*2+2].lazy_coef += dat[index].lazy_coef;
      }
    }
    dat[index].lazy = EMPTY;
    dat[index].lazy_coef = 0;
  }
 
  inline void value_update(int index){ dat[index].value = dat[index*2+1].value + dat[index*2+2].value; }

  void _update(int a,int b,char opr,int v,int index,int L,int R){
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a )return;
    if( a <= L && R <= b ){
      dat[index].lazy = opr; // 今いるノードに遅延を設定して処理をしてもらう
      if( opr == 'A' )      dat[index].lazy_coef += v; 
      lazy_evaluate(index,L,R);
      return;
    }
 
    _update(a,b,opr,v,index*2+1,L,(L+R)/2);
    _update(a,b,opr,v,index*2+2,(L+R)/2,R);
    value_update(index);

  }

  void update(int a,int b,char opr,int v){ _update(a,b,opr,v,0,0,limit); } 

  int _query(int a,int b,int index,int L,int R){
    lazy_evaluate(index,L,R);
 
    if( b <= L || R <= a ) return 0;
    if( a <= L && R <= b ) return dat[index].value;

    int tmp1 = _query(a,b,index*2+1,L,(L+R)/2);
    int tmp2 = _query(a,b,index*2+2,(L+R)/2,R);
    int ret = tmp1+tmp2;
    value_update(index);
    return ret;
  }

  int query(int a,int b) { return _query(a,b,0,0,limit); }

};


// Heavy Light Decomposition - begin

int chainNumber;
vector<int> subsize;
vector<int> chainID;
vector<int> headID;
vector<int> baseArray;
vector<int> posInBase;
vector<int> parent;

void HLD_dfs(int cur,int prev){
  parent[cur] = prev;
  rep(i,(int)G[cur].size()){
    int to = G[cur][i].to;
    if( to == prev ) continue;
    HLD_dfs(to,cur);
    subsize[cur] += subsize[to];
  }
}

void HLD(int cur,int prev,int &ptr){
  
  if( headID[chainNumber] == -1 ) headID[chainNumber] = cur;
  chainID[cur] = chainNumber;
  baseArray[ptr] = costs[cur];
  posInBase[cur] = ptr++;
  
  int maxi = -1;
  rep(i,(int)G[cur].size()) {
    int to = G[cur][i].to;
    if( to == prev ) continue;
    if( maxi == -1 || subsize[to] > subsize[maxi] ) maxi = to;
  }

  if( maxi != -1 ) HLD(maxi,cur,ptr);
  
  rep(i,(int)G[cur].size()){
    int to = G[cur][i].to;
    if( to == prev || to == maxi ) continue;
    ++chainNumber;
    HLD(to,cur,ptr);
  }

}

void HLD_init(){
  chainNumber = 0;

  subsize.clear();
  chainID.clear();
  headID.clear();
  baseArray.clear();
  posInBase.clear();
  parent.clear();

  subsize.resize(V,1);
  chainID.resize(V,-1);
  headID.resize(V,-1);
  baseArray.resize(V,-IINF);
  posInBase.resize(V,-1);
  parent.resize(V,-1);

  HLD_dfs(0,-1);
  int ptr = 0;
  HLD(0,-1,ptr);

}

// Heavy Light Decomposition - end

void _Change(int s,int t,int value,RMQ &rmq){
  int chain_s, chain_t = chainID[t];
  while( 1 ){
    chain_s = chainID[s];
    if( chain_s == chain_t ) {
      int ps = posInBase[s], pt = posInBase[t];
      rmq.update(min(ps,pt),max(ps,pt)+1,'A',value);
      return;
    } else {
      int head = headID[chain_s];
      int ps = posInBase[s], ph = posInBase[head];
      rmq.update(min(ps,ph),max(ps,ph)+1,'A',value);
      s = parent[head];
    }
  }
}

void Change(int s,int t,int value,RMQ &rmq,LCA_RMQ &lca_rmq){
  int ancestor = lca(s,t,lca_rmq);
  _Change(s,ancestor,value,rmq);
  _Change(t,ancestor,value,rmq);
  rmq.update(posInBase[ancestor],posInBase[ancestor]+1,'A',-value);
}

int main(){
  int T,Q,CNT=1;
  scanf("%d",&T);
  while( T-- ){
    scanf("%d",&V);
    rep(i,MAX_V) G[i].clear();
    costs.clear();
    costs.resize(V,0);
    rep(i,V-1) {
      int s,t;
      scanf("%d %d",&s,&t);
      G[s].push_back((Edge){t,0,-1});
      G[t].push_back((Edge){s,0,-1});
    }
    HLD_init();
    RMQ rmq;
    rmq.init(V);
    rmq.build(baseArray);

    LCA_RMQ lca_rmq;
    LCA_init(V,lca_rmq);

    scanf("%d",&Q);

    rep(_,Q){
      int s,t,c;
      scanf("%d %d %d",&s,&t,&c);
      Change(s,t,c,rmq,lca_rmq);
    }

    printf("Case #%d:",CNT++);
    puts("");
    rep(i,V) { printf("%d",rmq.query(posInBase[i],posInBase[i]+1)); puts(""); }
  }
  return 0;
}