Codeforces #358 Div2 C
問題文
考察
・頂点をrootとして,頂点は頂点に,頂点は頂点に,..., 頂点は頂点につながっているとする。
・以上から
を頂点から頂点までの間のedgeのcostの合計の最大値として,
が成り立つ。
・あとはrootから辺を辿ってそれぞれの葉まで探索しながら、辺のコストを足していきながらmaxes[v]を求めていく。そして、a[v] < maxes[v]なら削除する。
・もし,が削除されるなら以降の頂点も削除される。
参考:
Editorial:http://codeforces.com/blog/entry/45491
kmjp.hatenablog.jp
ソースコード
解説見て解いた。
DFSで解いてる人が多い中BFSっぽく解いてた。
あと無向グラフから有向グラフに変えてたけどそんな必要なかった...。
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.NoSuchElementException; import java.util.Queue; public class C { int N; int[] a; ArrayList<Edge>[] graph; private class Edge{ int v,c; public Edge(int v,int c){ this.v = v; this.c = c; } } private class P{ int v; long max; public P(int v,long max){ this.v = v; this.max = max; } } public ArrayList<Edge>[] directGraph(){ Queue<Integer> q = new ArrayDeque<Integer>(); q.offer(1); boolean[] used = new boolean[N + 1]; ArrayList<Edge>[] newGraph = new ArrayList[N + 1]; for(int i = 0;i <= N;i++){ newGraph[i] = new ArrayList<Edge>(); } used[1] = true; while(q.size() > 0){ int cur = q.poll(); for(Edge edge : graph[cur]){ if(used[edge.v])continue; used[edge.v] = true; newGraph[cur].add(new Edge(edge.v,edge.c)); q.offer(edge.v); } } return newGraph; } public void solve() { N = nextInt(); a = new int[N + 1]; for(int i = 0;i < N;i++){ a[i + 1] = nextInt(); } graph = new ArrayList[N + 1]; for(int i = 0;i < N + 1;i++){ graph[i] = new ArrayList<Edge>(); } for(int i = 1;i <= N - 1;i++){ int p = nextInt(); int c = nextInt(); graph[i + 1].add(new Edge(p,c)); graph[p].add(new Edge(i + 1,c)); } graph = directGraph(); Queue<P> q = new ArrayDeque<P>(); long[] maxes = new long[N + 1]; q.offer(new P(1,0)); while(q.size() > 0){ P p = q.poll(); for(Edge edge : graph[p.v]){ maxes[edge.v] = Math.max(maxes[edge.v],Math.max(maxes[p.v] + edge.c,edge.c)); q.offer(new P(edge.v,maxes[edge.v])); } } Queue<Integer> qq = new ArrayDeque<Integer>(); int ans = 0; qq.offer(1); while(qq.size() > 0){ int v = qq.poll(); ans++; for(Edge edge : graph[v]){ if(a[edge.v] < maxes[edge.v])continue; qq.offer(edge.v); } } out.println(N - ans); } public static void main(String[] args) { out.flush(); new C().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }