Submission #3225513
Source Code Expand
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; class Main{ static List<Integer> edges[]; static int[] leaf; static int[] maxpath; static int[] secpath; static void dfs(int v, int p){ if(edges[v].size()==1){ leaf[v]=1; maxpath[v]=1; return; }else if(edges[v].size()==2 && p!=-1){ int u = edges[v].get(0)+edges[v].get(1)-p; dfs(u, v); leaf[v]=leaf[u]; maxpath[v]=maxpath[u]+1; return; }else{ for(int u: edges[v])if(u!=p){ dfs(u, v); leaf[v] += leaf[u]; if(maxpath[u]>maxpath[v]){ secpath[v]=maxpath[v]; maxpath[v]=maxpath[u]; }else if(maxpath[u]>secpath[v]){ secpath[v]=maxpath[u]; } } } } static int ans=0; static void dfs2(int v, int p, int l){ // out.println(v+" "+leaf[v]+" "+maxpath[v]+" "+secpath[v]); if(secpath[v]>0){ int res = l+leaf[v]+maxpath[v]+secpath[v]-2; if(p==-1&&edges[v].size()==2)res++; ans=Math.max(ans, res); } for(int u: edges[v])if(u!=p)dfs2(u, v, l+leaf[v]-leaf[u]); } static void solve(){ int n = ni(); leaf = new int[n]; maxpath = new int[n]; secpath = new int[n]; edges = new List[n]; for(int i=0;i<n;++i)edges[i]=new ArrayList<>(); for(int i=0;i<n-1;++i){ int p=ni()-1, q=ni()-1; edges[p].add(q); edges[q].add(p); } int root = 0; for(int i=0;i<n;++i)if(edges[i].size()>1)root=i; dfs(root, -1); dfs2(root, -1, 0); out.println(ans); } public static void main(String[] args){ solve(); out.flush(); } private static InputStream in = System.in; private static PrintWriter out = new PrintWriter(System.out); static boolean inrange(int y, int x, int h, int w){ return y>=0 && y<h && x>=0 && x<w; } @SuppressWarnings("unchecked") static<T extends Comparable> int lower_bound(List<T> list, T key){ int lower=-1;int upper=list.size(); while(upper - lower>1){ int center =(upper+lower)/2; if(list.get(center).compareTo(key)>=0)upper=center; else lower=center; } return upper; } @SuppressWarnings("unchecked") static <T extends Comparable> int upper_bound(List<T> list, T key){ int lower=-1;int upper=list.size(); while(upper-lower >1){ int center=(upper+lower)/2; if(list.get(center).compareTo(key)>0)upper=center; else lower=center; } return upper; } @SuppressWarnings("unchecked") static <T extends Comparable> boolean next_permutation(List<T> list){ int lastIndex = list.size()-2; while(lastIndex>=0 && list.get(lastIndex).compareTo(list.get(lastIndex+1))>=0)--lastIndex; if(lastIndex<0)return false; int swapIndex = list.size()-1; while(list.get(lastIndex).compareTo(list.get(swapIndex))>=0)swapIndex--; T tmp = list.get(lastIndex); list.set(lastIndex++, list.get(swapIndex)); list.set(swapIndex, tmp); swapIndex = list.size()-1; while(lastIndex<swapIndex){ tmp = list.get(lastIndex); list.set(lastIndex, list.get(swapIndex)); list.set(swapIndex, tmp); ++lastIndex;--swapIndex; } return true; } private static final byte[] buffer = new byte[1<<15]; private static int ptr = 0; private static int buflen = 0; private static boolean hasNextByte(){ if(ptr<buflen)return true; ptr = 0; try{ buflen = in.read(buffer); } catch (IOException e){ e.printStackTrace(); } return buflen>0; } private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);} private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;} private static double nd(){ return Double.parseDouble(ns()); } private static char nc(){ return (char)skip(); } private static String ns(){ StringBuilder sb = new StringBuilder(); for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b); return sb.toString(); } private static int[] nia(int n){ int[] res = new int[n]; for(int i=0;i<n;++i)res[i]=ni(); return res; } private static long[] nla(int n){ long[] res = new long[n]; for(int i=0;i<n;++i)res[i]=nl(); return res; } private static int ni(){ int res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } private static long nl(){ long res=0,b; boolean minus=false; while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); if(b=='-'){ minus=true; b=readByte(); } for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); return minus ? -res:res; } }
Submission Info
Submission Time | |
---|---|
Task | K - Problem on Tree |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 4999 Byte |
Status | AC |
Exec Time | 214 ms |
Memory | 56352 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 70 ms | 20436 KB |
sample_02.txt | AC | 69 ms | 21076 KB |
subtask1_01.txt | AC | 162 ms | 35600 KB |
subtask1_02.txt | AC | 148 ms | 30552 KB |
subtask1_03.txt | AC | 127 ms | 25300 KB |
subtask1_04.txt | AC | 131 ms | 28436 KB |
subtask1_05.txt | AC | 120 ms | 28756 KB |
subtask1_06.txt | AC | 97 ms | 18772 KB |
subtask1_07.txt | AC | 183 ms | 50228 KB |
subtask1_08.txt | AC | 124 ms | 25556 KB |
subtask1_09.txt | AC | 142 ms | 32760 KB |
subtask1_10.txt | AC | 140 ms | 34408 KB |
subtask1_11.txt | AC | 130 ms | 29596 KB |
subtask1_12.txt | AC | 107 ms | 24020 KB |
subtask1_13.txt | AC | 101 ms | 21332 KB |
subtask1_14.txt | AC | 97 ms | 18388 KB |
subtask1_15.txt | AC | 190 ms | 50516 KB |
subtask1_16.txt | AC | 206 ms | 54188 KB |
subtask1_17.txt | AC | 195 ms | 53496 KB |
subtask1_18.txt | AC | 214 ms | 52588 KB |
subtask1_19.txt | AC | 191 ms | 54552 KB |
subtask1_20.txt | AC | 191 ms | 51964 KB |
subtask1_21.txt | AC | 204 ms | 54196 KB |
subtask1_22.txt | AC | 197 ms | 55984 KB |
subtask1_23.txt | AC | 202 ms | 54956 KB |
subtask1_24.txt | AC | 203 ms | 52888 KB |
subtask1_25.txt | AC | 202 ms | 53068 KB |
subtask1_26.txt | AC | 201 ms | 50896 KB |
subtask1_27.txt | AC | 208 ms | 50892 KB |
subtask1_28.txt | AC | 207 ms | 56352 KB |
subtask1_29.txt | AC | 206 ms | 54472 KB |
subtask1_30.txt | AC | 201 ms | 53536 KB |
subtask1_31.txt | AC | 206 ms | 52296 KB |
subtask1_32.txt | AC | 206 ms | 51728 KB |
subtask1_33.txt | AC | 211 ms | 51504 KB |
subtask1_34.txt | AC | 206 ms | 54304 KB |
subtask1_35.txt | AC | 191 ms | 50620 KB |
subtask1_36.txt | AC | 203 ms | 51944 KB |
subtask1_37.txt | AC | 207 ms | 53136 KB |
subtask1_38.txt | AC | 207 ms | 51584 KB |
subtask1_39.txt | AC | 202 ms | 55072 KB |