結果
問題 | No.1098 LCAs |
ユーザー |
|
提出日時 | 2020-06-26 22:40:22 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,259 ms / 2,000 ms |
コード長 | 19,724 bytes |
コンパイル時間 | 3,906 ms |
コンパイル使用メモリ | 92,340 KB |
実行使用メモリ | 98,056 KB |
最終ジャッジ日時 | 2024-11-17 23:45:37 |
合計ジャッジ時間 | 21,525 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import java.util.*;import java.io.*;import java.math.*;public class Main {static class Graph0n {private ArrayList<Node0n> dt = new ArrayList<>();Graph0n(int sz){for(int i=0; i<sz; i++){Node0n node1 = new Node0n();dt.add(node1);}}public void add(int vn, int val){ dt.get(vn).add(val); }public void add2(int vn, int val){ dt.get(vn).add(val);dt.get(val).add(vn);}public int get(int vn, int index){ return dt.get(vn).get(index); }public ArrayList<Integer> get(int vn){ return dt.get(vn).getAll(); }public int sizeOf(int vn){ return dt.get(vn).size(); }public void clear(){ for(int i=0; i<dt.size(); i++){ dt.get(i).clear(); } }}static class Node0n { //重みなし無向・有向グラフの頂点private ArrayList<Integer> next_vs = new ArrayList<>();public void add(int val){ next_vs.add(val); }public int get(int ad){ return next_vs.get(ad); }public ArrayList<Integer> getAll(){ return next_vs; }public int size(){ return next_vs.size(); }public void clear(){ next_vs.clear(); }}static class Edge {int from=-1, v2=-1; long weight;public Edge(int vn, long w){this.v2 = vn;this.weight = w;}public Edge(int cm, int vn, long w){this.from = cm;this.v2 = vn;this.weight = w;}}static class Edge2 {int v2; long cost1,cost2;public Edge2(int vn, long w1, long w2){this.v2 = vn;this.cost1 = w1;this.cost2 = w2;}}static class Comparator_Edge implements Comparator<Edge>{public int compare(Edge a, Edge b){if(a.weight>b.weight) return -1;else if(a.weight<b.weight) return 1;else return a.v2-b.v2;}}static class Vector {int x,y;public Vector(int sx, int sy){this.x=sx;this.y=sy;}}//私が好きなアルゴリズム::累積和・UF木//PriorityQueueは拡張for文で出すとsortされてない順番で出てくるよpublic static void main(String[] args) throws Exception {FastScanner sc = new FastScanner();PrintWriter out = new PrintWriter(System.out);int n=sc.nexI();Graph0n tree = new Graph0n(n);//根っこは頂点0for(int i=1; i<n; i++){int v1 = sc.nexI()-1;int w1 = sc.nexI()-1;tree.add2(v1,w1);}int[] deach = depth_on_root_tree(n, tree, 0);Queue<Edge> todo = new PriorityQueue<>(new Comparator_Edge());for(int i=0; i<n; i++){todo.add(new Edge(i, deach[i]));}long[] ans = new long[n];long[] num_inc_self = new long[n];fill(num_inc_self,0);while(todo.size()>0){Edge e = todo.poll();int vthis = e.v2;long sum2 = 0;long powsum = 0;for(int e2: tree.get(vthis)){sum2 += num_inc_self[e2];powsum += pow2(num_inc_self[e2]);}num_inc_self[vthis] = sum2+1;sum2 *= sum2;ans[vthis] = (sum2-powsum);ans[vthis] += num_inc_self[vthis]*2-1;}prtlnas(ans);out.flush();}private static int[] depth_on_root_tree(int n, Graph0n tree, int root){int[] deach = new int[n];fill(deach,-1);deach[root]=0;ArrayDeque<Integer> from_shallow = new ArrayDeque<>();from_shallow.add(root);from_shallow.add(-1);int dnow=1;while(from_shallow.size()>1){int dw = from_shallow.poll();if(dw==-1){dnow++;from_shallow.add(-1);}else{for(int e: tree.get(dw)){if(deach[e]<0){deach[e]=dnow;from_shallow.add(e);}}}}return deach;}private static boolean triangle_inequality(int a, int b, int c){if((a+b)<c) return false;if((b+c)<a) return false;if((c+a)<b) return false;return true;}private static int INF = (int)1e8;private static long INFL = (long)1e17;private static long e97 = (long)1e9 + 7;private static int abs(int a){ return (a>=0) ? a: -a; }private static long abs(long a){ return (a>=0) ? a: -a; }private static double abs(double a){ return (a>=0) ? a: -a; }private static int min(int a, int b){ return (a>b) ? b : a; }private static long min(long a, long b){ return (a>b) ? b : a; }private static double min(double a, double b){ return (a>b) ? b : a; }private static int max(int a, int b){ return (a>b) ? a : b; }private static long max(long a, long b){ return (a>b) ? a : b; }private static double max(double a, double b){ return (a>b) ? a : b; }private static int minN(int... ins){int min = ins[0];for(int i=1; i<ins.length; i++){ if(ins[i] < min) min = ins[i]; }return min;}private static int maxN(int... ins){int max = ins[0];for(int i=1; i<ins.length; i++){ if(ins[i] > max) max = ins[i]; }return max;}private static long minN(long... ins){long min = ins[0];for(int i=1; i<ins.length; i++){ if(ins[i] < min) min = ins[i]; }return min;}private static long maxN(long... ins){long max = ins[0];for(int i=1; i<ins.length; i++){ if(ins[i] > max) max = ins[i]; }return max;}private static int minExAd(int[] dt, int ad){int min=INF;for(int i=0; i<dt.length; i++){ if((i != ad) && (dt[i] < min)) min = dt[i]; }return min;}private static long minExAd(long[] dt, int ad){long min=INFL;for(int i=0; i<dt.length; i++){ if((i != ad) && (dt[i] < min)) min = dt[i]; }return min;}private static int minExVal(int[] dt, int ex_val){int min=INF;for(int i=0; i<dt.length; i++){ if((dt[i] != ex_val) && (dt[i] < min)) min = dt[i]; }return min;}private static long minExVal(long[] dt, long ex_val){long min=INFL;for(int i=0; i<dt.length; i++){ if((dt[i] != ex_val) && (dt[i] < min)) min = dt[i]; }return min;}private static int maxExAd(int[] dt, int ad){int max=-INF;for(int i=0; i<dt.length; i++){ if((i != ad) && (dt[i] > max)) max = dt[i]; }return max;}private static long maxExAd(long[] dt, int ad){long max=-INFL;for(int i=0; i<dt.length; i++){ if((i != ad) && (dt[i] > max)) max = dt[i]; }return max;}private static int maxExVal(int[] dt, int ex_val){int max=-INF;for(int i=0; i<dt.length; i++){ if((dt[i] != ex_val) && (dt[i] > max)) max = dt[i]; }return max;}private static long maxExVal(long[] dt, long ex_val){long max=-INFL;for(int i=0; i<dt.length; i++){ if((dt[i] != ex_val) && (dt[i] > max)) max = dt[i]; }return max;}private static boolean same3(long a, long b, long c){if(a!=b) return false;if(b!=c) return false;if(c!=a) return false;return true;}private static boolean dif3(long a, long b, long c){if(a==b) return false;if(b==c) return false;if(c==a) return false;return true;}private static double hypod(double a, double b){return Math.sqrt(a*a+b*b);}private static long factorial(int n) {long ans=1;for(long i=n; i>0; i--){ ans*=i; }return ans;}private static long facP(int n, long p) {long ans=1;for(long i=n; i>0; i--){ans*=i;ans %= p;}return ans;}private static long lcm(long m, long n){long ans = m/gcd(m,n);ans *= n;return ans;}private static long gcd(long m, long n) {if(m < n) return gcd(n, m);if(n == 0) return m;return gcd(n, m % n);}private static boolean is_prime(long a){if(a==1) return false;for(int i=2; i<=Math.sqrt(a); i++){ if(a%i == 0) return false; }return true;}private static long modinv(long a, long p) { //a|p, >1に注意long b = p, u = 1, v = 0;while (b>0) {long t = a / b;long pe = a%b;a=b; b=pe;pe= u-t*v;u=v; v=pe;}u %= p;if (u < 0) u += p;return u;}private static long[] fac10E97 = null;private static long[] finv10E97 = null;private static void Cinit(int max_sz, long p){fac10E97 = new long[max_sz+1];finv10E97 = new long[max_sz+1];fac10E97[0]=1;finv10E97[0]=1;for(int i=1; i<=max_sz; i++){fac10E97[i] = (fac10E97[i-1]*i) % p;}finv10E97[max_sz] = modinv(fac10E97[max_sz], p);for(int i=max_sz; i>1; i--){finv10E97[i-1] = (finv10E97[i]*i) % p;}}private static long C10e97(int n, int k, long p){long ans = fac10E97[n];ans *= finv10E97[k];ans %= p;ans *= finv10E97[n-k];ans %=p;if(ans<0) return ans+p;else return ans;}private static long C10e97LS(long n, int k, long p){long ans =1;for(long i=n; i>(n-(long)k); i--){ans *= i;ans %= e97;}ans *= modinv(facP(k,e97),e97);return ans%e97;}private static int pow(int n, int k){int ans=1;for(int i=0; i<k; i++) ans *= n;return ans;}private static int pow2(int in){ return in*in; }private static long pow2(long in){ return in*in; }private static double pow2(double in){ return in*in; }private static int getDigit2(long num){long cf = 1; int d=0;while(num >= cf){ d++; cf = 1<<d; }return d; //numはd桁の数で、2^dより小さい}private static int getDigit10(long num){long cf = 1; int d=0;while(num >= cf){ d++; cf*=10; }return d; //numはd桁の数で、10^dより小さい}private static boolean isINF(int in){if(((long)in*20)>INF) return true;else return false;}private static boolean isINFL(long in){if((in*10000)>INFL) return true;else return false;}private static long pow10E97(long ob, long soeji, long p){if(ob==0) return 0;if(soeji==0) return 1;if(soeji==2) return (ob*ob)%p;int d = getDigit2(soeji);long[] ob_pow_2pow = new long[d];ob_pow_2pow[0] = ob;for(int i=1; i<d; i++){ ob_pow_2pow[i] = (ob_pow_2pow[i-1]*ob_pow_2pow[i-1])%p; }long ans=1;for(int i=d-1; i>=0; i--){if(soeji >= (long)(1<<i)){soeji -= (long)(1<<i);ans = (ans*ob_pow_2pow[i])%p;}}return ans;}private static int flag(int pos){ return (1<<pos); }private static boolean isFlaged(int bit, int pos){if((bit&(1<<pos)) > 0) return true;else return false;}private static boolean isFlaged(long bit, int pos){if((bit&(1<<pos)) > 0) return true;else return false;}private static int deflag(int bit, int pos){ return bit&~(1<<pos); }private static int countFlaged(int bit){int ans=0;for(int i=0; i<getDigit2(bit); i++){if((bit&(1<<i)) > 0) ans++;}return ans;}private static void showflag(int bit){for(int i=0; i<getDigit2(bit); i++){if(isFlaged(bit,i)) System.out.print("O");else System.out.print(".");}System.out.println();}public static int biSearch(int[] dt, int target){int left=0, right=dt.length-1;int mid=-1;while(left<=right){mid = (right+left)/2;if(dt[mid] == target) return mid;if(dt[mid] < target) left=mid+1;else right=mid-1;}return -1;}public static int biSearchMax(long[] dt, long target){int left=-1, right=dt.length;int mid=-1;while((right-left)>1){mid = left + (right-left)/2;if(dt[mid] <= target) left=mid;else right=mid;}return left;//target以下の最大のaddress}public static int biSearchMaxAL(ArrayList<Integer> dt, long target){int left=-1, right=dt.size();int mid=-1;while((right-left)>1){mid = left + (right-left)/2;if(dt.get(mid) <= target) left=mid;else right=mid;}return left;//target以下の最大のaddress}private static int get_root_uf(int[] parent, int index){if(parent[index] == index) return index;int root = get_root_uf(parent, parent[index]);parent[index] = root;return root;}private static boolean is_same_uf(int[] parent, int x, int y){if(get_root_uf(parent,x) == get_root_uf(parent,y)) return true;else return false;}private static void unite_uf(int[] parent, int receiver, int attacker){parent[get_root_uf(parent,attacker)] = get_root_uf(parent, receiver);}private static int[] Xdir4 = {1,0,0,-1};private static int[] Ydir4 = {0,1,-1,0};private static int[] Xdir8 = {1,1,1,0,0,-1,-1,-1};private static int[] Ydir8 = {1,0,-1,1,-1,1,0,-1};private static boolean is_in_area(int y, int x, int h, int w){if(y<0) return false;if(x<0) return false;if(y>=h) return false;if(x>=w) return false;return true;}static void show2(boolean[][] dt, int lit_x, int lit_y){PrintWriter out = new PrintWriter(System.out);for(int j=0; j<dt.length; j++){for(int i=0; i<dt[j].length; i++){if((i==lit_y) && (j==lit_x)) out.print("X");else if(dt[j][i]) out.print("O");else out.print(".");}out.println();}out.flush();}static void show2(int[][] dt, String cmnt){PrintWriter out = new PrintWriter(System.out);for(int i=0; i<dt.length; i++){for(int j=0; j<dt[i].length; j++){out.print(dt[i][j]+",");}out.println("<-"+cmnt+":"+i);}out.flush();}static void show2(long[][] dt, String cmnt){PrintWriter out = new PrintWriter(System.out);for(int i=0; i<dt.length; i++){for(int j=0; j<dt[i].length; j++){out.print(dt[i][j]+",");}out.println("<-"+cmnt+":"+i);}out.flush();}static void disp_que(ArrayDeque<Long> dt){ //上手くいかなかった時用long a=0;while(dt.size()>0){a=dt.removeFirst();System.out.print(a);}System.out.println("\n");}static void disp_list(List dt){ //上手くいかなかった時用for(int i=0; i<dt.size(); i++){System.out.print(dt.get(i)+",");}System.out.println("\n");}private static void prtlnas(int[] as){PrintWriter out = new PrintWriter(System.out);for(int i=0; i<as.length; i++){out.println(as[i]);}out.flush();}private static void prtlnas(long[] as){PrintWriter out = new PrintWriter(System.out);for(int i=0; i<as.length; i++){out.println(as[i]);}out.flush();}private static void prtspas(int[] as){PrintWriter out = new PrintWriter(System.out);out.print(as[0]);for(int i=1; i<as.length; i++){out.print(" "+as[i]);}out.flush();}private static void prtspas(long[] as){PrintWriter out = new PrintWriter(System.out);out.print(as[0]);for(int i=1; i<as.length; i++){out.print(" "+as[i]);}out.flush();}private static void fill(boolean[] ob, boolean res){ for(int i=0; i<ob.length; i++){ ob[i] = res; }}private static void fill(int[] ob, int res){ for(int i=0; i<ob.length; i++){ ob[i] = res; }}private static void fill(long[] ob, long res){ for(int i=0; i<ob.length; i++){ ob[i] = res; }}private static void fill(char[] ob, char res){ for(int i=0; i<ob.length; i++){ ob[i] = res; }}private static void fill(double[] ob, double res){ for(int i=0; i<ob.length; i++){ ob[i] = res; }}private static void fill(boolean[][] ob,boolean res){for(int i=0;i<ob.length; i++){ for(int j=0; j<ob[0].length; j++){ ob[i][j] = res; }}}private static void fill(int[][] ob, int res){ for(int i=0; i<ob.length; i++){ for(int j=0; j<ob[0].length; j++){ ob[i][j] = res; }}}private static void fill(long[][] ob, long res){ for(int i=0; i<ob.length; i++){ for(int j=0; j<ob[0].length; j++){ ob[i][j] = res; }}}private static void fill(char[][] ob, char res){ for(int i=0; i<ob.length; i++){ for(int j=0; j<ob[0].length; j++){ ob[i][j] = res; }}}private static void fill(double[][] ob, double res){for(int i=0; i<ob.length; i++){ for(int j=0; j<ob[0].length; j++){ ob[i][j] = res; }}}private static void fill(int[][][] ob,int res){for(int i=0;i<ob.length;i++){for(int j=0;j<ob[0].length;j++){for(int k=0;k<ob[0][0].length;k++){ob[i][j][k]=res;}}}}private static void fill_parent(int[] ob){for(int i=0; i<ob.length; i++) ob[i]=i;}static class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;}else{ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}public String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while(isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nexL() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while(true){if ('0' <= b && b <= '9') {n *= 10;n += b - '0';}else if(b == -1 || !isPrintableChar(b) || b == ':'){return minus ? -n : n;}else{throw new NumberFormatException();}b = readByte();}}public int nexI() {long nl = nexL();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}public double nexD() { return Double.parseDouble(next());}public void ni(long[] array2){for(int i=0; i<array2.length; i++){array2[i] = nexL();}return;}public void ni(int[] array2){for(int i=0; i<array2.length; i++){array2[i] = nexI();}return;}public void ni(int[] as, int[] bs){for(int i=0; i<as.length; i++){as[i] = nexI();bs[i] = nexI();}return;}public void ni(int[] as, int[] bs, int[] cs){for(int i=0; i<as.length; i++){as[i] = nexI();bs[i] = nexI();cs[i] = nexI();}return;}}}