本文主要是介绍fzu 2277 Change 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Time Limit: 2000 mSec Memory Limit : 262144 KB
Problem Description
There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.
Initially all the node’s value is 0.
We have q operations. There are two kinds of operations.
1 v x k : a[v]+=x , a[v’]+=x-k (v’ is child of v) , a[v’’]+=x-2*k (v’’ is child of v’) and so on.
2 v : Output a[v] mod 1000000007(10^9 + 7).
Input
First line contains an integer T (1 ≤ T ≤ 3), represents there are T test cases.
In each test case:
The first line contains a number n.
The second line contains n-1 number, p2,p3,…,pn . pi is the father of i.
The third line contains a number q.
Next q lines, each line contains an operation. (“1 v x k” or “2 v”)
1 ≤ n ≤ 3*10^5
1 ≤ pi < i
1 ≤ q ≤ 3*10^5
1 ≤ v ≤ n; 0 ≤ x < 10^9 + 7; 0 ≤ k < 10^9 + 7
Output
For each operation 2, outputs the answer.
Sample Input
Sample Output
Source
第八届福建省大学生程序设计竞赛-重现赛（感谢承办方厦门理工学院）
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Task().solve();}
}class Task {InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final long Mod = 1000000007L ;List<Integer>[] adj ; int[] left , right , deep ;int time ;void dfs(int u , int dep){left[u] = ++time ;deep[u] = dep ;for(int v : adj[u]){dfs(v , dep+1) ;}right[u] = time ;}long[] add , addSum , sub , subSum ;void down(int t){if(add[t] != 0){add[t<<1] += add[t] ;add[t<<1] %= Mod ;add[t<<1|1] += add[t] ;add[t<<1|1] %= Mod ;addSum[t<<1] += add[t] ;addSum[t<<1] %= Mod ;addSum[t<<1|1] += add[t] ;addSum[t<<1|1] %= Mod ;add[t] = 0 ;}if(sub[t] != 0){sub[t<<1] += sub[t] ;sub[t<<1] %= Mod ;sub[t<<1|1] += sub[t] ;sub[t<<1|1] %= Mod ;subSum[t<<1] += sub[t] ;subSum[t<<1] %= Mod ;subSum[t<<1|1] += sub[t] ;subSum[t<<1|1] %= Mod ;sub[t] = 0 ;}}void update(int L , int R , long toAdd , long toSub , int l , int r , int t){if(L <= l && r <= R){add[t] += toAdd ;add[t] %= Mod ;addSum[t] += toAdd ;addSum[t] %= Mod ;sub[t] += toSub ;sub[t] %= Mod ;subSum[t] += toSub ;subSum[t] %= Mod ;return ;}down(t) ;int m = (l + r) >> 1 ;if(L <= m){update(L, R, toAdd, toSub, l, m, t<<1) ;}if(R > m){update(L, R, toAdd, toSub, m+1, r, t<<1|1) ;}}long query(int i , int l , int r , int t , int dep){if(l == r){long reslut = addSum[t] - subSum[t] * dep % Mod ;reslut %= Mod ;reslut = (reslut + Mod) % Mod ;return reslut ;}down(t) ;int m = (l + r) >> 1 ;if(i <= m){return query(i, l, m, t<<1 , dep) ;}else{return query(i, m+1, r, t<<1|1, dep) ;}}void solve(){int t = in.nextInt() ;while(t-- > 0){int n = in.nextInt() ;adj = new List[n+1] ;for(int i = 1 ; i <= n ; i++){adj[i] = new ArrayList<Integer>() ;}for(int i = 2 ; i <= n ; i++){adj[in.nextInt()].add(i) ;}left = new int[n+1] ;right = new int[n+1] ;deep = new int[n+1] ;add = new long[n<<2] ;addSum = new long[n<<2] ;sub = new long[n<<2] ;subSum = new long[n<<2] ;Arrays.fill(add, 0); Arrays.fill(addSum, 0); Arrays.fill(sub , 0); Arrays.fill(subSum , 0); time = 0 ; dfs(1 , 0) ;int q = in.nextInt() ;while(q-- > 0){if(in.nextInt() == 1){int u = in.nextInt() ;long x = in.nextLong() ;long k = in.nextLong() ;update(left[u] , right[u] , (x + deep[u] * k % Mod) % Mod, k, 1, n, 1) ;}else{int v = in.nextInt() ;out.println(query(left[v] , 1 , n , 1 , deep[v])) ;}}} out.flush() ;}
}class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = new StringTokenizer(""); } private void eat(String s) { tokenizer = new StringTokenizer(s); } public String nextLine() { try { return reader.readLine(); } catch (Exception e) { return null; } } public boolean hasNext() { while (!tokenizer.hasMoreTokens()) { String s = nextLine(); if (s == null) return false; eat(s); } return true; } public String next() { hasNext(); return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public int[] nextInts(int n) { int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = nextInt(); } return nums; } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public BigInteger nextBigInteger() { return new BigInteger(next()); } } 这篇关于fzu 2277 Change 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
