Problem B

Tree of Almost Clean Money

Input File: B.in

Output File: standard output

Time Limit: 4 seconds (C/C++)

Memory Limit: 256 megabytes

The tree of Almost Clean Money (or ACM Tree, for short) consists of N (1≤N≤500000) vertices in

which, well, (almost clean) money is growing (contrary to the old saying that money doesn’t grow

on trees). The vertices are numbered from 0 to N-1, with vertex 0 being the root of the tree. Every

vertex i except vertex 0 has a parent p(i) in the tree, such that p(i)<i. Initially, every vertex

contains v(i) (0≤v(i)<1000000007) monetary units. Due to its special properties, the tree has

attracted the attention of a large money laundering organization, who wants to use the tree for its

money “cleansing” business. This organization wants to execute Q (1≤Q≤50000) operations on

the tree. Each operation consists of two steps:

1) In step 1, K (1≤K≤1000) vertices from the tree are chosen: x(1), …, x(K) (0≤x(i)≤N-1) –

the same vertex may be selected multiple times here. In each of these vertices, an

amount of monetary units is added (thus increasing the amount of monetary units in

them). More exactly, y(i) (0≤y(i)<1000000007) monetary units are added to the selected

vertex x(i) (1≤i≤K).

2) In step 2, two vertices u and v (0≤u,v≤N-1) are chosen and the organization wants to

know the total amount of money found in the vertices located on the unique path in the

tree between the vertices u and v (with u and v inclusive).

The organization hired you to find the answer for step 2 of each of the Q operations and promised

you a hefty amount of money if you succeed.

Input

The first line of input contains the number of tree vertices N. The next N-1 lines contain two

space-separated integers, p(i) and i, each describing an edge of the tree. The next line contains

N space-separated values: the initial amount of monetary units in each vertex, v(0), …, v(N-1).

The next line contains the number of operations Q. Each of the next Q lines describes an

operation. Each operation is described by 9 space-separated integers, in this order: K, x(1), y(1),

A, B, C, D, u, v (0≤A,B,C,D<1000000007). The values x(2≤i≤K) and y(2≤i≤K) are generated as

follows:

x(i) = (A*x(i-1) + B) modulo N

y(i) = (C*y(i-1) + D) modulo 1000000007

Output

For each of the Q operations print a line containing the answer to step 2 of the operation. When

computing the answer for an operation, the effects of steps 1 from previous operations need to be

considered, too (i.e. after adding y(i) monetary units to a vertex x(i), these units remain added to

the vertex when executing subsequent operations, too).

acm

Sample input Sample output Explanation

4

0 1

0 3

1 2

1 2 3 4

3

1000 1 1 1 0 1 0 0 2

2 0 5 1 1 2 2 2 3

1 3 7 999 999 999 999 1 3

1006

1027

1031

In the first operation the value 1 is added

1000 times to vertex 1 (note A=C=1,

B=D=0). The path between 0 and 2

contains the vertices 0, 1 and 2. The total

amount of monetary units in them is 1006.

In operation 2: x(1)=0, y(1)=5, x(2)=1,

y(2)=12. The path between 2 and 3 contains

all the vertices of the tree.

In operation 3: K=1, so A, B, C, D are

irrelevant.

给你一棵n个节点的树（n<=5e5），现在可以进行至多Q次操作（Q<=5e4），每次至多可以给k个节点（k<=1000）增加一个数值，然后每个操作都有一个询问（u,v），问从u到v的简单路径上的节点权值和。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define MM(a,b) memset(a,b,sizeof(a));using namespace std;typedef long long ll;#define CT continue#define SC scanfconst int N=5*1e5+10;const double pi=acos(-1);int n,siz[N],dep[N],son[N],treepos[N],top[N],par[N],x[1005],y[1005];ll tree[N];vector
            
              G[N];void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u);}int dfs_clock;void dfs1(int u,int father,int depth){ siz[u]=1; dep[u]=depth; son[u]=-1; par[u]=father; for(int i=0;i
             
              siz[son[u]]) son[u]=v; }}void dfs2(int u,int tp){ top[u]=tp; treepos[u]=++dfs_clock; if(son[u]==-1) return; dfs2(son[u],tp); for(int i=0;i
              
               =1){ res+=tree[x]; x-=lowbit(x); } return res;}ll query(int a,int b){ if(a>b) swap(a,b); return tfind(b)-tfind(a-1);}ll ans(int u,int v){ ll res=0,tu=top[u],tv=top[v]; while(tu!=tv) { if(dep[tu]
              
             
            
           
          
         
        
       
      
     

　　分析：学了下树链剖分，树连剖分主要是用于对树进行路径求和统计以及去最大值最小值之类的，第一次dfs，找到重儿子，并给

节点深度表好号，记录下每个节点额父节点，，第二次dfs，构建树链，同时建好BIT或线段树，，最后然后路径求和的时候，先要统计链顶节点深度大的。