白駿検疫所(13209)

検疫所
今回のココア豆5号問題で似たような問題が発生しました.(これはバイナリツリーで、範囲の小さいツリーに限られています)

1.ヒント

1)ある人が感染した場合,感染する可能性のある人はその人が住んでいる都市に住んでいる人と,その都市で検疫所がつながっていない都市に住んでいる人である。

2)一般的な解決策がなかなか見つからないため,最終的にはすべての場合を試みるしかない.グループに含まれる最大頂点の重み付け和が与えられた場合、グレーの解法で解くことができます。

3)f(x)=f(x)=f(x)=重みのセットの和がxxxを超えない場合、検査ステーションはKKKを超えないものを収容できるかどうか。このように定義すると,f(x)f(x)f(x)f(x)は単調増分関数であり,二分探索が可能である.

2.近接

似たような問題を解いたことがありますか。

その他のレッスン
他のレッスンの問題は、ブルーレイのサイズを最小にしてすべてのレッスンを含めることです.この問題も「伝染病の拡散に対応するため、政府が備蓄する治療剤の個数」が検疫所に分けられた集団の中で最大集団の人口数の和であるため、最大集団の人口数が最も少ないKK検疫所が設置された場合、最大集団の人口数がどれだけ少ないかという問題である.
他の授業の問題は一度に問題の答えを見つけるのは難しいですが、ブルーレイの大きさが与えられていると入れられるかどうかがわかりやすいので、それを利用して二分探索を行いました.
この問題も可能ですか.

問題を分解できますか?

どちらの都市も1つの経路しか通れないというので、問題から分かるように、与えられた都市は木です.
木は再帰的な性質を持っているので,問題を分解することができる.ある頂点を基準に自分の子供を乗せると思ったら、まずすべての子供を詰めて、それから最大の始まりから、絶えず最適な解を求めることができます.以下の貪欲な選択属性を証明することができる.pppは現在、断子絶孫の頂点であり、cccは子供である.

まず、組み立てることができれば、最大限に組み立てることがメリットであることを証明します.最適解が最大限含まれない方法で作成されると仮定します.pppが属する組合せは、実はc 1 c 1 c 1とc 2 c 2を含むことができるが、すでに切断されている.

切断したものを連続した年に変更してもKKKは減少するので無条件が有利です.
では、最大から切断するのが最適であることをどのように証明しますか?
同様に,ある最適解は大きなものから始まるのではなく,一つの方法で生じる.

c 1 c 1 c 1はc 2 c 2が属する集団人口より大きいが、c 1 c 1 c 1を切断した.私がこのように選んだのは、最高の年だと言った.

最適解は、より小さなエッジを含むように変換できます.
pppが属する集団の人口数は元の答えより小さくなるので,c 1 c 1 c 1,c 2 c 2も同様である.
このように答えを変えるのは,決して損をしない.

3.実施

public class Main {
	static int[] S; static long M;
	static ArrayList<ArrayList<Integer>> adj;
	static int cnt;
	
	// here 루트로 하는 트리를 정점의 가중치의 합이 M을 넘지 않게
	// 최적의 방법으로 나누고 here이 속한 그룹의 가중치의 합을 반환
	static long postorder(int here, int parent) {
		long sum = S[here];
		PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int there : adj.get(here)) {
			if (there == parent) continue;
			long t = postorder(there, here);
			sum += t; pq.offer(t);
		}
		// 어차피 끊어내야 한다면 큰거부터 끊어낸다
		while (!pq.isEmpty() && sum > M) { sum -= pq.poll(); cnt++; }
		return sum;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder ans = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		while (TC-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			S = new int[N + 1];
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 1; i <= N; i++) S[i] = Integer.parseInt(st.nextToken());
			adj = new ArrayList<>(N);
			for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
			for (int i = 0; i < N - 1; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				adj.get(u).add(v); adj.get(v).add(u);
			}
			// f(x) = 한 그룹의 가중치의 합이 x가 넘지 않게,
			// 최적의 방법으로 잘랐을 때 자르는 횟수가 K를 넘지 않게 자를 수 있는지 여부
			// f(lo) = false f(hi) = true인 hi를 반환
			long lo = 0; long hi = 100000000000000L;
			int max = 0;
			for (int i = 1; i <= N; i++) max = Math.max(max, S[i]);
			while (lo + 1 < hi) {
				long mid = (lo + hi) / 2;
				M = mid; cnt = 0;
				postorder(1, 1);
				if (max <= mid && cnt <= K) hi = mid;
				else lo = mid;
			}
			ans.append(hi).append("\n");
		}
		System.out.print(ans);
	}
	
}

1）時間複雑度

ツリーのループプロセスは正確には1回の頂点のみにアクセスするため、全体のNNN回のアクセスであり、隣接線はN21 N-1 N21011であり、チェックするたびにlgnlgnlgnの優先順位キューが挿入される.切断の過程も何回切断しなければならなくて、やっと何本の幹線を切断することができます.
このプローブの上限は101410^{14}1014なのでN×lgN×lg1014N\times lgN\times lg10^{14}N×lgN×lg1014

2）テストケース