****Tywins Tactics Solved

Tywins Tactics

Tywin Lannister is a tactical genius. At the heart of his tactical skills, is the way he has organized his armies, and the way he is able to estimate his soldiers' skill-levels, thus helping him make crucial decisions as to whom to dispatch to which areas of the war.

His army is organized in the form of a hierarchy - indeed it is a tree, with him as the root. We say "A has immediate superior B" if A reports directly to B. We further say "A has superior B" if there is a chain of soldiers starting with A, ending with B, and where each soldier reports directly to the next soldier of the chain. Further, each soldier is assigned an initial skill-level based on prior experience and battle proficiency.

In order for Tywin to decide whom to send to which battle, he has the following scheme: He chooses a particular soldier S as the leader of his temporary 'regiment', and sends in to battle, S as well as all the soldiers that have S as one of their superiors. He estimates the skill level of the regiment as the total skill level of all the soldiers under S (denoted by query "Q S").

After a battle, he may want to update the skill levels of some soldiers. If he wants to update the skill level of soldier S to value x, it is denoted by the query "U S x".

You are given the structure of the army, whose size is N, the initial skill levels of all the individual soldiers, as well the number of queries M. For each query of the type "Q S", report the sum of skill-levels of all the soldiers who have S as their superior.

Note: The soldiers are numbered 1 to N, and Tywin is given the number 1.

Input

The first line consists of the integers N and M, denoting the number of soldiers and the number of queries.

This is followed by a single line consisting of N nonnegative values - the skill levels of the N soldiers.

This is then followed by N-1 lines consisting of pairs of integers (u, v), denoting that either u is an immediate superior of v, or vice-versa.

Finally you are given the M queries, of either the form "U S x" or "Q S".

Output

For each "Q S" query, output the sum of skill values of all the soldiers under S.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁵
• All skill values given with be in the range [0, 20,000]
• 1 ≤ S ≤ N for all queries
• All soldiers will have soldier 1 (Tywin) as their superior

Example

Input:
5 8
7 2 0 5 8
1 2
2 3
2 4
1 5
Q 1
Q 2
U 2 4
Q 1
Q 2
U 5 3
Q 1
Q 2

Output:
22
7
24
9
19
9

*******************************************EDITORIAL****************************************************************

Pre-requisites:

dfs, range sum queries

Problem:

You are given a rooted tree T, associate with each vertex v a weight skill[v]. Also given are a set of queries of either the form "update skill of v to x", or "what is the sum of skill values of vertices in the subtree of v". For each query of the second form, return the answer.

Quick Explanation:

Map the given vertex numbers to [1...N] such that the subtree rooted at any vertex has all mapped values in a contiguous range. Then updates of the first form imply changing skill-values at the given mapped number, and queries of the second form are simply range sum queries in the appropriate range, that can be answered using either a segment tree or a binary indexed tree.

The mapping of vertices that satisfy the given property can be done using dfs numbers (in-times/out-times). For details, see the Explanation section which draws an analogy to a bracketed expression.

Overall time complexity:
O(N) - finding out the mapping and the required range for each node O(M logN) - to carry out each query: either point update, or range sum query.

Detailed Explanation:

For an illustration, let us consider the following tree:

   1
  / \
 2   5
    / \
   3   6
    \
     4


From the above, I can form a bracketed expression of the form:
(x1 + (x2) + (x5 + (x3 + (x4)) + (x6))) Whenever I go down the tree, I am opening a bracket, whenever I go up the tree, I am closing a bracket. I am also giving "variables" that will correspond to skill-values for each node.

Seeing the above, I can rewrite 1,2,3,4,5 by mapping them to values as seen from left to right:
1 -> 1
2 -> 2
5 -> 3
3 -> 4
4 -> 5
6 -> 6

Now, in the mapped version, the bracketed expression looks like:
(y1 + (y2) + (y3 + (y4 + (y5)) + (y6)))

We are here interested in queries of two types:
Type1: change value of x[i], or in other words, y[mapped(i)]
Type2: Find the total in the complete bracket "defined" by i, which is y[mapped(i)] + y[mapped(i)+1] + ... + y[end_range(i)], for suitable mapped(i) and end_range(i).

The good thing to note is, type2 is now a query over values in a range. This can be done by a segment tree or a binary indexed tree! We only need what the range is, given each vertex.

Finding out the range, as well as the mapping, can be done easily by dfs-times. The dfs-time for a node is the value of a time-counter when that node was visited. Indeed, if you ran a dfs on the given tree, it will visit the nodes in the order "1-2-5-3-4-6" itself! The range is then just starting from the current point, and ending at the latest time a node was visited. This information can be returned in the dfs function, as in the following pseudocode:
int dfs(node v, int time)
    mapping[v] = time
    ret = time
    for(c is a child of v)
        ret = dfs(c, ret+1) //give it the next "time"-point, and get the latest time point of the child for future
    begin_range[v] = time
    end_range[v] = ret
    return ret

Calling the above with dfs(1, 1) will do all the magic for you!

Finally, a BIT pseudocode implementation of the rest of the problem:
void update(int S, int x)
    BIT.increment(mapping[S], x - skill[S])
    skill[S] = x;

int query(int S)
    return BIT.query(end_range[S]) - BIT.query(begin_range[S]-1)


Alternate Approach:

This approach was used by some contestants. It is summarized as follows:

Step 1: Perform a heavy-light decomposition of the tree.
Step 2: Initialize each node with the value that is the sum of the skill-levels of its subtree.
Step 3: For each "U S x" query, add "skill[S]-x" to the nodes along the path from S to the root. Due to Heavy-light decomposition structure, this can be done in O(logN ^ 2) time. Also update the value of skill[S].
Step 4: For each "Q S" query, return the value stored in the node S.





********************************************CODE***********************************************************************



#include<iostream>

using namespace std;

typedef long long int lli;

#include<bits/stdc++.h>

list<lli> li[1000000];

lli gen[1000000];

vector<pair<lli,lli> > v;

lli end=0;

  lli arr[1000000+10];

  lli visited[10000000];

  lli start=0;

  lli indx=0;

  lli t[10000000];

  

  

  void build(lli node, lli a, lli b)

     {

    if(a>b) return;

 if (a==b)

 {

  t[node]=gen[a];

  return;

 }

 

 build(node*2, a, (a+b)/2);

 build(node*2+1,(a+b)/2+1,b);

 

  t[node]=t[node*2]+t[node*2+1];

   }




lli  query(lli node, lli a, lli b, lli i, lli j)

{

 if(a>b||a>j||b<i) return 0;

 

 if (a>=i && b<=j) return t[node];

 

 lli q1=query(node*2, a, (a+b)/2, i, j);

 lli q2=query(node*2+1, (a+b)/2+1, b, i, j);

 

 return q1+q2;

}




void update(lli node, lli a, lli b, lli i, lli j,  lli inc)

{

 if(a>b) return;

 

 if(a>b||a>j||b<i) return;

 

 if (a>=i && b<=j)

 {

  t[node]=inc;

  

  return;

 }

 

 update(node*2, a, (a+b)/2, i, j, inc);

 update(node*2+1, (a+b)/2+1, b,i, j, inc);

 t[node] = t[node*2] + t[node*2+1];

}







/* ARRAY GENERATION PART *//////////

void dfs(lli node)

{

   end++;

   start++;

    

       gen[indx]=arr[node];

       

   //   cout<<" seting gen[indx] "<< gen[indx]<<endl;

       indx++;

       v[node].first=start;

 

    list<lli>:: iterator it;

    for(it=li[node].begin();it!=li[node].end();it++)

     {

       // cout<<" trying "<<*it<<endl;

      

      if(!visited[*it])

       {

         //cout<<" get "<<*it<<endl;

        visited[*it]=1;

        dfs(*it);

       }

     }

  //    cout<<"finalizing "<<node<<" with start  and end time "<<start<<" "<<end<<endl;

    // v[node].first=start;

     v[node].second=end;

     

}

int main()

 {

   

   

   lli n,m;

   cin>>n>>m;



   for(lli i=1;i<=n;i++)

    {

      cin>>arr[i];

    }

    

    v.push_back(make_pair(0,0));

    for(lli i=1;i<n;i++)

     {

      v.push_back(make_pair(0,0));

       lli a,b;

        cin>>a>>b;

        li[a].push_back(b);

        li[b].push_back(a);

  }

  v.push_back(make_pair(0,0));

   //cout<<" dfs call "<<endl;

   visited[1]=1;

  dfs(1);

  build(1,0,n-1);

  

  

 // for(lli i=0;i<n;i++)cout<<gen[i]<<endl;

 

 for(lli i=1;i<=m;i++)

  {

  

  char c;

   cin>>c;

   if(c=='Q')

    {

     lli node ;

      cin>>node;

     // cout<<" query for  node "<<node<<" range "<<v[node].first<<" "<<v[node].second<<endl;

      lli ans=query(1,0,n-1,v[node].first-1,v[node].second-1);

       cout<<ans<<endl;

    }

    else

    {

      lli a,b;

       cin>>a>>b;

       update(1,0,n-1,v[a].first-1,v[a].first-1,b);

    }

     

  }

  

    return 0;

 }