{"id":"c0f3e686-5fd6-4e6d-94eb-642293dff79d","name":"Path Sum","description":"You are given a tree with n nodes (numbered from 1 to n), node 1 is the root of tree.\r\nEach node has a value say Vi is the value of i'th node.\r\n\r\nYou have to perform q queries of two types:-\r\n1 i v : change the value of i'th node to v,\r\n2 i : add all nodes on path from root to i'th node.","inputFormat":"First line contains single integer n.\r\nsecond line contains n integers v1 v2 v3 .... vn\r\nthird line contains n-1 integers p2 p3 p4 ... pn here pi is the parent of i'th node\r\nfourth line contains single int q\r\nq following lines contains queries of type 1 and 2","outputFormat":"of every query of type 2 print sum of values.","constraints":"1. 1 &lt;= N &lt;= 10^5\r\n2. 1 &lt;= Vi &lt;= 10^4\r\n3. 1 &lt;= q &lt;= 10^4","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static InputReader in = new InputReader(System.in);\r\n static PrintWriter out = new PrintWriter(System.out);\r\n\r\n public static void main(String[] args) throws IOException {\r\n\r\n // write your code here\r\n\r\n\r\n out.close();\r\n }\r\n\r\n private static class InputReader implements AutoCloseable {\r\n\r\n private static final int DEFAULT_BUFFER_SIZE = 1 << 16;\r\n\r\n\r\n private static final InputStream DEFAULT_STREAM = System.in;\r\n\r\n private static final int MAX_DECIMAL_PRECISION = 21;\r\n\r\n private int c;\r\n\r\n private final byte[] buf;\r\n private final int bufferSize;\r\n private int bufIndex;\r\n private int numBytesRead;\r\n\r\n private final InputStream stream;\r\n\r\n private static final byte EOF = -1;\r\n\r\n private static final byte NEW_LINE = 10;\r\n\r\n private static final byte SPACE = 32;\r\n\r\n private static final byte DASH = 45;\r\n\r\n private static final byte DOT = 46;\r\n private char[] charBuffer;\r\n private static final byte[] bytes = new byte[58];\r\n private static final int[] ints = new int[58];\r\n private static final char[] chars = new char[128];\r\n\r\n static {\r\n char ch = '' '';\r\n int value = 0;\r\n byte _byte = 0;\r\n for (int i = 48; i < 58; i++)\r\n bytes[i] = _byte++;\r\n for (int i = 48; i < 58; i++)\r\n ints[i] = value++;\r\n for (int i = 32; i < 128; i++)\r\n chars[i] = ch++;\r\n }\r\n\r\n public InputReader() {\r\n this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);\r\n }\r\n public InputReader(int bufferSize) {\r\n this(DEFAULT_STREAM, bufferSize);\r\n }\r\n public InputReader(InputStream stream) {\r\n this(stream, DEFAULT_BUFFER_SIZE);\r\n }\r\n public InputReader(InputStream stream, int bufferSize) {\r\n if (stream == null || bufferSize <= 0)\r\n throw new IllegalArgumentException();\r\n buf = new byte[bufferSize];\r\n charBuffer = new char[128];\r\n this.bufferSize = bufferSize;\r\n this.stream = stream;\r\n }\r\n private byte read() throws IOException {\r\n\r\n if (numBytesRead == EOF)\r\n throw new IOException();\r\n\r\n if (bufIndex >= numBytesRead) {\r\n bufIndex = 0;\r\n numBytesRead = stream.read(buf);\r\n if (numBytesRead == EOF)\r\n return EOF;\r\n }\r\n\r\n return buf[bufIndex++];\r\n }\r\n private int readJunk(int token) throws IOException {\r\n\r\n if (numBytesRead == EOF)\r\n return EOF;\r\n do {\r\n\r\n while (bufIndex < numBytesRead) {\r\n if (buf[bufIndex] > token)\r\n return 0;\r\n bufIndex++;\r\n }\r\n numBytesRead = stream.read(buf);\r\n if (numBytesRead == EOF)\r\n return EOF;\r\n bufIndex = 0;\r\n\r\n } while (true);\r\n\r\n }\r\n public byte nextByte() throws IOException {\r\n return (byte) nextInt();\r\n }\r\n public int nextInt() throws IOException {\r\n\r\n if (readJunk(DASH - 1) == EOF)\r\n throw new IOException();\r\n int sgn = 1, res = 0;\r\n\r\n c = buf[bufIndex];\r\n if (c == DASH) {\r\n sgn = -1;\r\n bufIndex++;\r\n }\r\n\r\n do {\r\n\r\n while (bufIndex < numBytesRead) {\r\n if (buf[bufIndex] > SPACE) {\r\n res = (res << 3) + (res << 1);\r\n res += ints[buf[bufIndex++]];\r\n } else {\r\n bufIndex++;\r\n return res * sgn;\r\n }\r\n }\r\n numBytesRead = stream.read(buf);\r\n if (numBytesRead == EOF)\r\n return res * sgn;\r\n bufIndex = 0;\r\n\r\n } while (true);\r\n\r\n }\r\n public int[] nextIntArray(int n) throws IOException {\r\n int[] ar = new int[n];\r\n for (int i = 0; i < n; i++)\r\n ar[i] = nextInt();\r\n return ar;\r\n }\r\n public int[] nextIntArray1(int n) throws IOException {\r\n int[] ar = new int[n + 1];\r\n for (int i = 1; i <= n; i++)\r\n ar[i] = nextInt();\r\n return ar;\r\n }\r\n public void close() throws IOException {\r\n stream.close();\r\n }\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"8\r\n4 7 9 5 2 1 3 5 \r\n1 1 1 4 3 4 1 \r\n7\r\n1 4 3\r\n1 3 8\r\n2 7\r\n1 4 6\r\n1 1 7\r\n2 3\r\n2 4\r\n","sampleOutput":"10\r\n15\r\n13\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"debe0517-0a6b-4d6b-b283-3f14ab81501d","name":"Euler Tour For Experts","slug":"euler-tour-for-experts-1013","type":0},{"id":"32cb5069-0eff-43dd-a897-0cc0209dd790","name":"Path Sum","slug":"path-sum","type":1}],"next":null,"prev":{"id":"8abb7d80-a349-4e05-8287-419da05dc634","name":"Count Descendants","type":1,"slug":"count-descendants"}}}

Path Sum

You are given a tree with n nodes (numbered from 1 to n), node 1 is the root of tree. Each node has a value say Vi is the value of i'th node. You have to perform q queries of two types:- 1 i v : change the value of i'th node to v, 2 i : add all nodes on path from root to i'th node.

{"id":"c0f3e686-5fd6-4e6d-94eb-642293dff79d","name":"Path Sum","description":"You are given a tree with n nodes (numbered from 1 to n), node 1 is the root of tree.\r\nEach node has a value say Vi is the value of i'th node.\r\n\r\nYou have to perform q queries of two types:-\r\n1 i v : change the value of i'th node to v,\r\n2 i : add all nodes on path from root to i'th node.","inputFormat":"First line contains single integer n.\r\nsecond line contains n integers v1 v2 v3 .... vn\r\nthird line contains n-1 integers p2 p3 p4 ... pn here pi is the parent of i'th node\r\nfourth line contains single int q\r\nq following lines contains queries of type 1 and 2","outputFormat":"of every query of type 2 print sum of values.","constraints":"1. 1 &lt;= N &lt;= 10^5\r\n2. 1 &lt;= Vi &lt;= 10^4\r\n3. 1 &lt;= q &lt;= 10^4","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static InputReader in = new InputReader(System.in);\r\n static PrintWriter out = new PrintWriter(System.out);\r\n\r\n public static void main(String[] args) throws IOException {\r\n\r\n // write your code here\r\n\r\n\r\n out.close();\r\n }\r\n\r\n private static class InputReader implements AutoCloseable {\r\n\r\n private static final int DEFAULT_BUFFER_SIZE = 1 << 16;\r\n\r\n\r\n private static final InputStream DEFAULT_STREAM = System.in;\r\n\r\n private static final int MAX_DECIMAL_PRECISION = 21;\r\n\r\n private int c;\r\n\r\n private final byte[] buf;\r\n private final int bufferSize;\r\n private int bufIndex;\r\n private int numBytesRead;\r\n\r\n private final InputStream stream;\r\n\r\n private static final byte EOF = -1;\r\n\r\n private static final byte NEW_LINE = 10;\r\n\r\n private static final byte SPACE = 32;\r\n\r\n private static final byte DASH = 45;\r\n\r\n private static final byte DOT = 46;\r\n private char[] charBuffer;\r\n private static final byte[] bytes = new byte[58];\r\n private static final int[] ints = new int[58];\r\n private static final char[] chars = new char[128];\r\n\r\n static {\r\n char ch = '' '';\r\n int value = 0;\r\n byte _byte = 0;\r\n for (int i = 48; i < 58; i++)\r\n bytes[i] = _byte++;\r\n for (int i = 48; i < 58; i++)\r\n ints[i] = value++;\r\n for (int i = 32; i < 128; i++)\r\n chars[i] = ch++;\r\n }\r\n\r\n public InputReader() {\r\n this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);\r\n }\r\n public InputReader(int bufferSize) {\r\n this(DEFAULT_STREAM, bufferSize);\r\n }\r\n public InputReader(InputStream stream) {\r\n this(stream, DEFAULT_BUFFER_SIZE);\r\n }\r\n public InputReader(InputStream stream, int bufferSize) {\r\n if (stream == null || bufferSize <= 0)\r\n throw new IllegalArgumentException();\r\n buf = new byte[bufferSize];\r\n charBuffer = new char[128];\r\n this.bufferSize = bufferSize;\r\n this.stream = stream;\r\n }\r\n private byte read() throws IOException {\r\n\r\n if (numBytesRead == EOF)\r\n throw new IOException();\r\n\r\n if (bufIndex >= numBytesRead) {\r\n bufIndex = 0;\r\n numBytesRead = stream.read(buf);\r\n if (numBytesRead == EOF)\r\n return EOF;\r\n }\r\n\r\n return buf[bufIndex++];\r\n }\r\n private int readJunk(int token) throws IOException {\r\n\r\n if (numBytesRead == EOF)\r\n return EOF;\r\n do {\r\n\r\n while (bufIndex < numBytesRead) {\r\n if (buf[bufIndex] > token)\r\n return 0;\r\n bufIndex++;\r\n }\r\n numBytesRead = stream.read(buf);\r\n if (numBytesRead == EOF)\r\n return EOF;\r\n bufIndex = 0;\r\n\r\n } while (true);\r\n\r\n }\r\n public byte nextByte() throws IOException {\r\n return (byte) nextInt();\r\n }\r\n public int nextInt() throws IOException {\r\n\r\n if (readJunk(DASH - 1) == EOF)\r\n throw new IOException();\r\n int sgn = 1, res = 0;\r\n\r\n c = buf[bufIndex];\r\n if (c == DASH) {\r\n sgn = -1;\r\n bufIndex++;\r\n }\r\n\r\n do {\r\n\r\n while (bufIndex < numBytesRead) {\r\n if (buf[bufIndex] > SPACE) {\r\n res = (res << 3) + (res << 1);\r\n res += ints[buf[bufIndex++]];\r\n } else {\r\n bufIndex++;\r\n return res * sgn;\r\n }\r\n }\r\n numBytesRead = stream.read(buf);\r\n if (numBytesRead == EOF)\r\n return res * sgn;\r\n bufIndex = 0;\r\n\r\n } while (true);\r\n\r\n }\r\n public int[] nextIntArray(int n) throws IOException {\r\n int[] ar = new int[n];\r\n for (int i = 0; i < n; i++)\r\n ar[i] = nextInt();\r\n return ar;\r\n }\r\n public int[] nextIntArray1(int n) throws IOException {\r\n int[] ar = new int[n + 1];\r\n for (int i = 1; i <= n; i++)\r\n ar[i] = nextInt();\r\n return ar;\r\n }\r\n public void close() throws IOException {\r\n stream.close();\r\n }\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"8\r\n4 7 9 5 2 1 3 5 \r\n1 1 1 4 3 4 1 \r\n7\r\n1 4 3\r\n1 3 8\r\n2 7\r\n1 4 6\r\n1 1 7\r\n2 3\r\n2 4\r\n","sampleOutput":"10\r\n15\r\n13\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"debe0517-0a6b-4d6b-b283-3f14ab81501d","name":"Euler Tour For Experts","slug":"euler-tour-for-experts-1013","type":0},{"id":"32cb5069-0eff-43dd-a897-0cc0209dd790","name":"Path Sum","slug":"path-sum","type":1}],"next":null,"prev":{"id":"8abb7d80-a349-4e05-8287-419da05dc634","name":"Count Descendants","type":1,"slug":"count-descendants"}}}
plane

Editor


Loading...

Path Sum

medium

You are given a tree with n nodes (numbered from 1 to n), node 1 is the root of tree. Each node has a value say Vi is the value of i'th node. You have to perform q queries of two types:- 1 i v : change the value of i'th node to v, 2 i : add all nodes on path from root to i'th node.

Constraints

1. 1 <= N <= 10^5 2. 1 <= Vi <= 10^4 3. 1 <= q <= 10^4

Format

Input

First line contains single integer n. second line contains n integers v1 v2 v3 .... vn third line contains n-1 integers p2 p3 p4 ... pn here pi is the parent of i'th node fourth line contains single int q q following lines contains queries of type 1 and 2

Output

of every query of type 2 print sum of values.

Example

Sample Input

8 4 7 9 5 2 1 3 5 1 1 1 4 3 4 1 7 1 4 3 1 3 8 2 7 1 4 6 1 1 7 2 3 2 4

Sample Output

10 15 13

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode