白俊陽救出作戦(16437)

両救作戦

1.ヒント

1)「島ごとに1番島までのルートが唯一」と、島は木の条件を満たしています。

2)すべての数の島について,経路に移動することにより,時間を超えることは避けられない.

3)木の再帰的性質を利用して,ある頂点に到達する量の個数を求め,再帰的に表すことができる.

2.近接

問題を分解できますか?

問題は「島ごとに1番島までの経路が唯一」ということですが、どうしてこれらのNNN個島が木であることを知っていますか?
ツリー内のすべての頂点間のパスは、一意のグラフィックです.島ごとに1番島への経路があるので、1番島を通過点とすれば、すべての島の間の経路は唯一であるしかない.
木なので、どの頂点をつかんで根と呼ぶのも全く無理なので、1番頂点を根と呼んで、すべての羊が住んでいる島から親までの幹線に沿って移動することができます.

ただし、ツリーはこのような形で存在し、接続リストに近づくことができます.このように全量移動する時間的複雑度はO(N 2)O(N^2)O(N 2)である.
では、ツリーの遍歴を利用して、一度だけアクセスして頂点を解く問題を定義します.
f(n)=f(n)=f(n)=f(n)=nnn番頂点到達可能な数
このように定義すると,f(1)f(1)f(1)f(1))は我々が要求する値となる.f(n)f(n)fを求めるために

3.実施

public class Main {
	static int[] parent;
	static ArrayList<ArrayList<Integer>> children;
	static int[] amount;
	
	// here을 루트로 하는 서브트리에서 루트에 도착하고 살아남는 양의 수
	static long inorder(int here) {
		long sum = amount[here];
		for (int ch : children.get(here)) sum += inorder(ch);
		return Math.max(sum, 0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		parent = new int[N + 1]; parent[1] = 1;
		children = new ArrayList<>(N + 1);
		for (int i = 0; i < N + 1; i++) children.add(new ArrayList<>());
		amount = new int[N + 1];
		for (int i = 2; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			String t = st.nextToken();
			amount[i] = Integer.parseInt(st.nextToken());
			if (t.equals("W")) amount[i] *= -1;
			int p = Integer.parseInt(st.nextToken());
			parent[i] = p;
			children.get(p).add(i);
		}
		System.out.println(inorder(1));
	}
	
}

1）時間複雑度

明らかに、inorderinoderinorder関数は頂点ごとに1回しか呼び出されません.しかし、子供を見回すとき、時間の複雑さはどのくらいですか?
いくらinoderinoderinoderinoder関数が呼び出されても、子女を巡回する回数は木に存在する幹線の個数と同じです.木の頂点がNNN個であれば、幹線はN 1 N−1 N個であるため、時間的複雑度はO(N+Nέ1)=O(N+N−1)=O(N+Nέ1)=O(N)である.

2）テストケース