tookunn’s diary

主に競技プログラミング関係

Codeforces #358 Div2 C

問題文

codeforces.com

考察

・頂点v_1をrootとして,頂点v_1は頂点v_2に,頂点v_2は頂点v_3に,..., 頂点v_{k - 1}は頂点v_{k}につながっているとする。

・以上から
maxes[v_k]を頂点v_1から頂点v_kまでの間のedgeのcostの合計の最大値として,
maxes[v_k] = max\{dist(v_1,v_k),dist(v_2,v_k),dist(v_3,v_k),...,dist(v_{k - 1},v_k)\}
が成り立つ。

・あとはrootから辺を辿ってそれぞれの葉まで探索しながら、辺のコストを足していきながらmaxes[v]を求めていく。そして、a[v] < maxes[v]なら削除する。

・もし,v_{k - 1}が削除されるならv_{k}以降の頂点も削除される。

参考:
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());
	}
}