daily pastebin goal
77%
SHARE
TWEET

Untitled

a guest Feb 24th, 2013 129 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.InputMismatchException;
  4.  
  5. /**
  6.  * Actual solution is at the top, in class Solver
  7.  */
  8. final public class test implements Runnable {
  9.         private static String[] args;
  10.  
  11.         public static void main(String[] args) {
  12.                 test.args = args;
  13.                 new Thread(null, new test(), "MyRunThread", 1 << 27).start();
  14.         }
  15.  
  16.         //@Override
  17.         public void run() {
  18.                 long time_beg = -1;
  19.                 InputStream inputStream = System.in;
  20.                 OutputStream outputStream = System.out;
  21.                 if (args.length > 0 && args[0].equals("outside")) {
  22.                         time_beg = System.currentTimeMillis();
  23.                         try {
  24.                                 inputStream = new FileInputStream("IO/in.txt");
  25. //                              outputStream = new FileOutputStream("IO/out.txt");
  26.                         } catch (Exception e) {
  27.                                 System.err.println(e);
  28.                                 System.exit(1);
  29.                         }
  30.                 } else {
  31.                         try {
  32. //                              inputStream = new FileInputStream("IO/in.txt");
  33. //                              outputStream = new FileOutputStream("IO/out.txt");
  34.                         } catch (Exception e) {
  35.                                 System.err.println(e);
  36.                                 System.exit(1);
  37.                         }
  38.                 }
  39.  
  40.                 Solver s = new Solver();
  41.                 s.in = new InputReader(inputStream);
  42.                 s.out = new OutputWriter(outputStream);
  43.                 if (args.length > 0 && args[0].equals("outside")) {
  44.                         s.dout = new DebugWriter(s.out);
  45.                 }
  46.  
  47.                 s.solve();
  48.  
  49.                 if (args.length > 0 && args[0].equals("outside")) {
  50.                         s.dout.printFormat("*** Total time: %.3f ***\n", (System.currentTimeMillis() - time_beg) / 1000.0);
  51.                 }
  52.  
  53.                 s.out.close();
  54.         }
  55. }
  56.  
  57.  
  58. final class Solver {
  59.         InputReader in;
  60.         OutputWriter out;
  61.         DebugWriter dout;
  62.         static int t[][];
  63.         static int sz[];
  64.         static int d[];
  65.         static int inTree[];
  66.         static int G[][];
  67.         static void dfs(int v, int p, int num, int depth)
  68.         {
  69.                 inTree[v]=num;
  70.                 sz[num]++;
  71.                 d[v]=depth;
  72.                 for (int i=0; i<G[v].length; ++i)
  73.                 {
  74.                         int to=G[v][i];
  75.                         if (to==p)
  76.                                 continue;
  77.                         dfs(to,v,num,depth+1);
  78.                 }
  79.         }
  80.         static int find(int p, int num)
  81.         {
  82.                 int res=0;
  83.                 for (int i=p; i>0; i-=(i&(-i)))
  84.                         res+=t[num][i];
  85.                 return res;
  86.         }
  87.         static void add(int p, int v, int num)
  88.         {
  89.                 for (int i=p; i<t[num].length; i+=(i&(-i)))
  90.                         t[num][i]+=v;
  91.         }
  92.         public void solve() {
  93.  
  94.                 int n= in.readInt();
  95.                 int q=in.readInt();
  96.                 int e[][]=new int [n-1][2];
  97.                 int degree[]=new int[n];
  98.                 for (int i=0; i<n-1; ++i)
  99.                 {
  100.                         int v1=in.readInt();
  101.                         int v2=in.readInt();
  102.                         v1--;
  103.                         v2--;
  104.                         degree[v1]++;
  105.                         degree[v2]++;
  106.                         e[i][0]=v1;
  107.                         e[i][1]=v2;
  108.                 }
  109.                 G=new int[n][];
  110.                 for (int i=0; i<n; ++i)
  111.                         G[i]=new int[degree[i]];
  112.                 for (int i=0; i<n-1; ++i)
  113.                 {
  114.                         int v1=e[i][0];
  115.                         int v2=e[i][1];
  116.                         G[v1][--degree[v1]]=v2;
  117.                         G[v2][--degree[v2]]=v1;
  118.                 }
  119.                 t=new int[G[0].length+1][];
  120.                 sz=new int[G[0].length];
  121.                 d=new int[n];
  122.                 inTree=new int[n];
  123.                 for (int i=0; i<G[0].length; ++i)
  124.                         dfs(G[0][i],0,i,1);
  125.                 for (int i=0; i<G[0].length; ++i)
  126.                         t[i]=new int[sz[i]+1];
  127.                 t[t.length-1]=new int[n+10];
  128.                 int inRoot=0;
  129.                 for (int i=0; i<q; ++i)
  130.                 {
  131.                         int ty=in.readInt();
  132.                         if (ty==0)
  133.                         {
  134.                                 int v=in.readInt();
  135.                                 v--;
  136.                                 int val=in.readInt();
  137.                                 int dist=in.readInt();
  138.                                 if (v==0)
  139.                                 {
  140.                                         inRoot+=val;
  141.                                         add(1,val,t.length-1);
  142.                                         add(dist+1,-val,t.length-1);
  143.                                 }
  144.                                 else
  145.                                 {
  146.                                         if (dist>=d[v])
  147.                                         {
  148.                                                 int left=dist-d[v];
  149.                                                 inRoot+=val;
  150.                                                 add(1,val,t.length-1);
  151.                                                 add(left+1,-val,t.length-1);
  152.                                                 add(left+1,val,inTree[v]);
  153.                                                 add(d[v]+dist+1,-val,inTree[v]);
  154.                                         }
  155.                                         else
  156.                                         {
  157.                                                 add(d[v]-dist,val,inTree[v]);
  158.                                                 add(d[v]+dist+1,-val,inTree[v]);
  159.                                         }
  160.                                 }
  161.                         }
  162.                         else
  163.                         {
  164.                                 int v=in.readInt();
  165.                                 v--;
  166.                                 if (v==0)
  167.                                         out.print(inRoot+"\n");
  168.                                 else
  169.                                         out.print(find(d[v],inTree[v])+find(d[v],t.length-1)+"\n");
  170.                         }
  171.                 }
  172.         }
  173.  
  174.  
  175.  
  176. }
  177.  
  178.  
  179. final class InputReader {
  180.         private boolean finished = false;
  181.  
  182.         private InputStream stream;
  183.         private byte[] buf = new byte[1 << 10];
  184.         private int curChar;
  185.         private int numChars;
  186.  
  187.         public InputReader(InputStream stream) {
  188.                 this.stream = stream;
  189.         }
  190.  
  191.         private int read() {
  192.                 if (numChars == -1)
  193.                         throw new InputMismatchException();
  194.                 if (curChar >= numChars) {
  195.                         curChar = 0;
  196.                         try {
  197.                                 numChars = stream.read(buf);
  198.                         } catch (IOException e) {
  199.                                 throw new InputMismatchException();
  200.                         }
  201.                         if (numChars <= 0)
  202.                                 return -1;
  203.                 }
  204.                 return buf[curChar++];
  205.         }
  206.  
  207.         public int peek() {
  208.                 if (numChars == -1)
  209.                         return -1;
  210.                 if (curChar >= numChars) {
  211.                         curChar = 0;
  212.                         try {
  213.                                 numChars = stream.read(buf);
  214.                         } catch (IOException e) {
  215.                                 return -1;
  216.                         }
  217.                         if (numChars <= 0)
  218.                                 return -1;
  219.                 }
  220.                 return buf[curChar];
  221.         }
  222.  
  223.         public int readInt() {
  224.                 int c = read();
  225.                 while (isSpaceChar(c))
  226.                         c = read();
  227.                 int sgn = 1;
  228.                 if (c == '-') {
  229.                         sgn = -1;
  230.                         c = read();
  231.                 }
  232.                 int res = 0;
  233.                 do {
  234.                         if (c < '0' || c > '9')
  235.                                 throw new InputMismatchException();
  236.                         res *= 10;
  237.                         res += c - '0';
  238.                         c = read();
  239.                 } while (!isSpaceChar(c));
  240.                 return res * sgn;
  241.         }
  242.  
  243.         public long readLong() {
  244.                 int c = read();
  245.                 while (isSpaceChar(c))
  246.                         c = read();
  247.                 int sgn = 1;
  248.                 if (c == '-') {
  249.                         sgn = -1;
  250.                         c = read();
  251.                 }
  252.                 long res = 0;
  253.                 do {
  254.                         if (c < '0' || c > '9')
  255.                                 throw new InputMismatchException();
  256.                         res *= 10;
  257.                         res += c - '0';
  258.                         c = read();
  259.                 } while (!isSpaceChar(c));
  260.                 return res * sgn;
  261.         }
  262.  
  263.         public String readString() {
  264.                 int c = read();
  265.                 while (isSpaceChar(c))
  266.                         c = read();
  267.                 StringBuilder res = new StringBuilder();
  268.                 do {
  269.                         res.appendCodePoint(c);
  270.                         c = read();
  271.                 } while (!isSpaceChar(c));
  272.                 return res.toString();
  273.         }
  274.  
  275.         public static boolean isSpaceChar(int c) {
  276.                 return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  277.         }
  278.  
  279.         private String readLine0() {
  280.                 StringBuilder buf = new StringBuilder();
  281.                 int c = read();
  282.                 while (c != '\n' && c != -1) {
  283.                         if (c != '\r')
  284.                                 buf.appendCodePoint(c);
  285.                         c = read();
  286.                 }
  287.                 return buf.toString();
  288.         }
  289.  
  290.         public String readLine() {
  291.                 String s = readLine0();
  292.                 while (s.trim().length() == 0)
  293.                         s = readLine0();
  294.                 return s;
  295.         }
  296.  
  297.         public String readLine(boolean ignoreEmptyLines) {
  298.                 if (ignoreEmptyLines)
  299.                         return readLine();
  300.                 else
  301.                         return readLine0();
  302.         }
  303.  
  304.         public BigInteger readBigInteger() {
  305.                 try {
  306.                         return new BigInteger(readString());
  307.                 } catch (NumberFormatException e) {
  308.                         throw new InputMismatchException();
  309.                 }
  310.         }
  311.  
  312.         public char readCharacter() {
  313.                 int c = read();
  314.                 while (isSpaceChar(c))
  315.                         c = read();
  316.                 return (char) c;
  317.         }
  318.  
  319.         public double readDouble() {
  320.                 int c = read();
  321.                 while (isSpaceChar(c))
  322.                         c = read();
  323.                 int sgn = 1;
  324.                 if (c == '-') {
  325.                         sgn = -1;
  326.                         c = read();
  327.                 }
  328.                 double res = 0;
  329.                 while (!isSpaceChar(c) && c != '.') {
  330.                         if (c == 'e' || c == 'E')
  331.                                 return res * Math.pow(10, readInt());
  332.                         if (c < '0' || c > '9')
  333.                                 throw new InputMismatchException();
  334.                         res *= 10;
  335.                         res += c - '0';
  336.                         c = read();
  337.                 }
  338.                 if (c == '.') {
  339.                         c = read();
  340.                         double m = 1;
  341.                         while (!isSpaceChar(c)) {
  342.                                 if (c == 'e' || c == 'E')
  343.                                         return res * Math.pow(10, readInt());
  344.                                 if (c < '0' || c > '9')
  345.                                         throw new InputMismatchException();
  346.                                 m /= 10;
  347.                                 res += (c - '0') * m;
  348.                                 c = read();
  349.                         }
  350.                 }
  351.                 return res * sgn;
  352.         }
  353.  
  354.         public boolean isExhausted() {
  355.                 int value;
  356.                 while (isSpaceChar(value = peek()) && value != -1)
  357.                         read();
  358.                 return value == -1;
  359.         }
  360. }
  361.  
  362. final class OutputWriter {
  363.         private final PrintWriter writer;
  364.  
  365.         public OutputWriter(OutputStream outputStream) {
  366.                 writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream), 1 << 10));
  367.         }
  368.  
  369.         public OutputWriter(Writer writer) {
  370.                 this.writer = new PrintWriter(writer);
  371.         }
  372.  
  373.  
  374.         public void print(Object... objects) {
  375.                 for (int i = 0; i < objects.length; i++) {
  376.                         if (i != 0)
  377.                                 writer.print(' ');
  378.                         writer.print(objects[i]);
  379.                 }
  380.         }
  381.  
  382.         public void printLine(Object... objects) {
  383.                 print(objects);
  384.                 writer.println();
  385.         }
  386.  
  387.         public void printFormat(String format, Object... objects) {
  388.                 writer.printf(format, objects);
  389.         }
  390.  
  391.  
  392.         public void print(char[] objects) {
  393.                 writer.print(objects);
  394.         }
  395.  
  396.         public void printLine(char[] objects) {
  397.                 writer.println(objects);
  398.         }
  399.  
  400.         public void printLine(char[][] objects) {
  401.                 for (int i = 0; i < objects.length; ++i)
  402.                         printLine(objects[i]);
  403.         }
  404.  
  405.  
  406.         public void print(int[] objects) {
  407.                 for (int i = 0; i < objects.length; i++) {
  408.                         if (i != 0)
  409.                                 writer.print(' ');
  410.                         writer.print(objects[i]);
  411.                 }
  412.         }
  413.  
  414.         public void printLine(int[] objects) {
  415.                 print(objects);
  416.                 writer.println();
  417.         }
  418.  
  419.         public void printLine(int[][] objects) {
  420.                 for (int i = 0; i < objects.length; ++i)
  421.                         printLine(objects[i]);
  422.         }
  423.  
  424.  
  425.         public void print(short[] objects) {
  426.                 for (int i = 0; i < objects.length; i++) {
  427.                         if (i != 0)
  428.                                 writer.print(' ');
  429.                         writer.print(objects[i]);
  430.                 }
  431.         }
  432.  
  433.         public void printLine(short[] objects) {
  434.                 print(objects);
  435.                 writer.println();
  436.         }
  437.  
  438.         public void printLine(short[][] objects) {
  439.                 for (int i = 0; i < objects.length; ++i)
  440.                         printLine(objects[i]);
  441.         }
  442.  
  443.  
  444.         public void print(long[] objects) {
  445.                 for (int i = 0; i < objects.length; i++) {
  446.                         if (i != 0)
  447.                                 writer.print(' ');
  448.                         writer.print(objects[i]);
  449.                 }
  450.         }
  451.  
  452.         public void printLine(long[] objects) {
  453.                 print(objects);
  454.                 writer.println();
  455.         }
  456.  
  457.         public void printLine(long[][] objects) {
  458.                 for (int i = 0; i < objects.length; ++i)
  459.                         printLine(objects[i]);
  460.         }
  461.  
  462.  
  463.         public void print(double[] objects) {
  464.                 for (int i = 0; i < objects.length; i++) {
  465.                         if (i != 0)
  466.                                 writer.print(' ');
  467.                         writer.print(objects[i]);
  468.                 }
  469.         }
  470.  
  471.         public void printLine(double[] objects) {
  472.                 print(objects);
  473.                 writer.println();
  474.         }
  475.  
  476.         public void printLine(double[][] objects) {
  477.                 for (int i = 0; i < objects.length; ++i)
  478.                         printLine(objects[i]);
  479.         }
  480.  
  481.  
  482.         public void print(byte[] objects) {
  483.                 for (int i = 0; i < objects.length; i++) {
  484.                         if (i != 0)
  485.                                 writer.print(' ');
  486.                         writer.print(objects[i]);
  487.                 }
  488.         }
  489.  
  490.         public void printLine(byte[] objects) {
  491.                 print(objects);
  492.                 writer.println();
  493.         }
  494.  
  495.         public void printLine(byte[][] objects) {
  496.                 for (int i = 0; i < objects.length; ++i)
  497.                         printLine(objects[i]);
  498.         }
  499.  
  500.  
  501.         public void print(boolean[] objects) {
  502.                 for (int i = 0; i < objects.length; i++) {
  503.                         if (i != 0)
  504.                                 writer.print(' ');
  505.                         writer.print(objects[i]);
  506.                 }
  507.         }
  508.  
  509.         public void printLine(boolean[] objects) {
  510.                 print(objects);
  511.                 writer.println();
  512.         }
  513.  
  514.         public void printLine(boolean[][] objects) {
  515.                 for (int i = 0; i < objects.length; ++i)
  516.                         printLine(objects[i]);
  517.         }
  518.  
  519.  
  520.         public void close() {
  521.                 writer.close();
  522.         }
  523.  
  524.         public void flush() {
  525.                 writer.flush();
  526.         }
  527. }
  528.  
  529. final class DebugWriter {
  530.         private final OutputWriter writer;
  531.  
  532.         public DebugWriter(OutputWriter writer) {
  533.                 this.writer = writer;
  534.         }
  535.  
  536.         private void printDebugMessage() {
  537.                 writer.print("DEBUG:\t");
  538.         }
  539.  
  540.  
  541.         public void printLine(Object... objects) {
  542.                 flush();
  543.                 printDebugMessage();
  544.                 writer.printLine(objects);
  545.                 flush();
  546.         }
  547.  
  548.         public void printFormat(String format, Object... objects) {
  549.                 flush();
  550.                 printDebugMessage();
  551.                 writer.printFormat(format, objects);
  552.                 flush();
  553.         }
  554.  
  555.  
  556.         public void printLine(char[] objects) {
  557.                 flush();
  558.                 printDebugMessage();
  559.                 writer.printLine(objects);
  560.                 flush();
  561.         }
  562.  
  563.         public void printLine(char[][] objects) {
  564.                 flush();
  565.                 for (int i = 0; i < objects.length; ++i)
  566.                         printLine(objects[i]);
  567.                 flush();
  568.         }
  569.  
  570.  
  571.         public void printLine(double[] objects) {
  572.                 flush();
  573.                 printDebugMessage();
  574.                 writer.printLine(objects);
  575.                 flush();
  576.         }
  577.  
  578.         public void printLine(double[][] objects) {
  579.                 flush();
  580.                 for (int i = 0; i < objects.length; ++i)
  581.                         printLine(objects[i]);
  582.                 flush();
  583.         }
  584.  
  585.  
  586.         public void printLine(int[] objects) {
  587.                 flush();
  588.                 printDebugMessage();
  589.                 writer.printLine(objects);
  590.                 flush();
  591.         }
  592.  
  593.         public void printLine(int[][] objects) {
  594.                 flush();
  595.                 for (int i = 0; i < objects.length; ++i)
  596.                         printLine(objects[i]);
  597.                 flush();
  598.         }
  599.  
  600.  
  601.         public void printLine(short[] objects) {
  602.                 flush();
  603.                 printDebugMessage();
  604.                 writer.printLine(objects);
  605.                 flush();
  606.         }
  607.  
  608.         public void printLine(short[][] objects) {
  609.                 flush();
  610.                 for (int i = 0; i < objects.length; ++i)
  611.                         printLine(objects[i]);
  612.                 flush();
  613.         }
  614.  
  615.  
  616.         public void printLine(long[] objects) {
  617.                 flush();
  618.                 printDebugMessage();
  619.                 writer.printLine(objects);
  620.                 flush();
  621.         }
  622.  
  623.         public void printLine(long[][] objects) {
  624.                 flush();
  625.                 for (int i = 0; i < objects.length; ++i)
  626.                         printLine(objects[i]);
  627.                 flush();
  628.         }
  629.  
  630.  
  631.         public void printLine(byte[] objects) {
  632.                 flush();
  633.                 printDebugMessage();
  634.                 writer.printLine(objects);
  635.                 flush();
  636.         }
  637.  
  638.         public void printLine(byte[][] objects) {
  639.                 flush();
  640.                 for (int i = 0; i < objects.length; ++i)
  641.                         printLine(objects[i]);
  642.                 flush();
  643.         }
  644.  
  645.  
  646.         public void printLine(boolean[] objects) {
  647.                 flush();
  648.                 printDebugMessage();
  649.                 writer.printLine(objects);
  650.                 flush();
  651.         }
  652.  
  653.         public void printLine(boolean[][] objects) {
  654.                 flush();
  655.                 for (int i = 0; i < objects.length; ++i)
  656.                         printLine(objects[i]);
  657.                 flush();
  658.         }
  659.  
  660.  
  661.         public void flush() {
  662.                 writer.flush();
  663.         }
  664. }
  665.  
  666.  
  667. final class Pair<F, S> {
  668.         public F first;
  669.         public S second;
  670.  
  671.         public Pair(F first, S second) {
  672.                 this.first = first;
  673.                 this.second = second;
  674.         }
  675.  
  676.         @Override
  677.         public int hashCode() {
  678.                 int hFirst = first != null ? first.hashCode() : 0;
  679.                 int hSecond = second != null ? second.hashCode() : 0;
  680.                 return 31 * hFirst + hSecond;
  681.         }
  682.  
  683.         @Override
  684.         public boolean equals(Object o) {
  685.                 if (this == o) return true;
  686.                 if (o == null || getClass() != o.getClass()) return false;
  687.  
  688.                 Pair pair = (Pair) o;
  689.  
  690.                 return (first != null ? first.equals(pair.first) : pair.first == null) &&
  691.                                 (second != null ? second.equals(pair.second) : pair.second == null);
  692.         }
  693.  
  694.         @Override
  695.         protected Object clone() throws CloneNotSupportedException {
  696.                 return new Pair<F, S>(first, second);
  697.         }
  698.  
  699.         @Override
  700.         public String toString() {
  701.                 return "(" + first + ", " + second + ")";
  702.         }
  703. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top