結果
問題 | No.806 木を道に |
ユーザー |
|
提出日時 | 2019-03-22 21:52:45 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 837 ms / 2,000 ms |
コード長 | 4,402 bytes |
コンパイル時間 | 2,110 ms |
コンパイル使用メモリ | 80,968 KB |
実行使用メモリ | 88,584 KB |
最終ジャッジ日時 | 2024-09-19 05:15:51 |
合計ジャッジ時間 | 15,973 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
import java.util.Scanner;import java.util.Collections;import java.util.ArrayList;import java.util.Arrays;import java.util.Queue;import java.util.ArrayDeque;import java.util.Deque;import java.util.PriorityQueue;import java.util.Set;import java.util.Map;import java.util.HashMap;import java.util.TreeSet;import java.util.Comparator;public class Main {static int mod = 1000000007;static int size = 510000;static long[] fac = new long[size];static long[] finv = new long[size];static long[] inv = new long[size];public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] a = new int[n-1];int[] b = new int[n-1];for(int i = 0; i < n-1; i++){a[i] = scanner.nextInt()-1;b[i] = scanner.nextInt()-1;}Map<Integer, Integer> map = new HashMap<Integer,Integer>();for(int i = 0; i < n-1; i++){if(!map.containsKey(a[i])){map.put(a[i], 1);}else{map.put(a[i], map.get(a[i])+1);}if(!map.containsKey(b[i])){map.put(b[i], 1);}else{map.put(b[i], map.get(b[i])+1);}}int count = 0;for(int val : map.values()){if(val == 1){count++;}}System.out.println(count-2);}static class Point{int x;int y;Point(int x, int y){x = this.x;y = this.y;}}//繰り返し二乗法public static long pow(long x, long n){long ans = 1;while(n > 0){if((n & 1) == 1){ans = ans * x;ans %= mod;}x = x * x % mod;n >>= 1;}return ans;}//fac, inv, finvテーブルの初期化、これ使う場合はinitComb()で初期化必要public static void initComb(){fac[0] = finv[0] = inv[0] = fac[1] = finv[1] = inv[1] = 1;for (int i = 2; i < size; ++i) {fac[i] = fac[i - 1] * i % mod;inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod;finv[i] = finv[i - 1] * inv[i] % mod;}}//nCk % modpublic static long comb(int n, int k){return fac[n] * finv[k] % mod * finv[n - k] % mod;}//n! % modpublic static long fact(int n){return fac[n];}//(n!)^-1 with % modpublic static long finv(int n){return finv[n];}static class Pair implements Comparable<Pair>{int x, y;Pair(int a, int b){x = a;y = b;}@Overridepublic boolean equals(Object o){if (this == o) return true;if (!(o instanceof Pair)) return false;Pair p = (Pair) o;return x == p.x && y == p.y;}@Overridepublic int compareTo(Pair p){//return x == p.x ? y - p.y : x - p.x; //xで昇順にソート//return (x == p.x ? y - p.y : x - p.x) * -1; //xで降順にソート//return y == p.y ? x - p.x : y - p.y;//yで昇順にソートreturn (y == p.y ? x - p.x : y - p.y)*-1;//yで降順にソート}}static class UnionFind {int[] parent;public UnionFind(int size) {parent = new int[size];Arrays.fill(parent, -1);}public boolean unite(int x, int y) {x = root(x);y = root(y);if (x != y) {if (parent[y] < parent[x]) {int tmp = y;y = x;x = tmp;}parent[x] += parent[y];parent[y] = x;return true;}return false;}public boolean same(int x, int y) {return root(x) == root(y);}public int root(int x) {return parent[x] < 0 ? x : (parent[x] = root(parent[x]));}public int size(int x) {return -parent[root(x)];}}public static int upperBound(long[] a,long val){return upperBound(a,0,a.length,val);}public static int upperBound(long[] a,int l,int r,long val){if(r-l==1){if(a[l]>val) return l;return r;}int mid=(l+r)/2;if(a[mid]>val){return upperBound(a,l,mid,val);}else{return upperBound(a,mid,r,val);}}public static int lowerBound(long[] a,long val){return lowerBound(a,0,a.length,val);}public static int lowerBound(long[] a,int l,int r,long val){if(r-l==1){if(a[l]<val) return r;return l;}int mid=(l+r)/2;if(a[mid]<val){return lowerBound(a,mid,r,val);}else{return lowerBound(a,l,mid,val);}}}