Advertisement
Guest User

Untitled

a guest
Feb 24th, 2013
602
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 13.72 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement