API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 24th, 2013
595
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 13.72 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!