Codeforces Round #551
3876 단어 Codeforces
http://codeforces.com/contest/1153/problem/D
방법:
dp[i]는 노드 i 가 얻 을 수 있 는 최대 치 를 나타 내 고 우 리 는 1 로 최대 치 를 얻 을 수 있 음 을 나타 내 며 2 는 큰 값 을 얻 을 수 있 음 을 나타 낸다.
j 는 i 의 하위 노드 이다.
가령 i 가 max,dp[i]=max(dp[j]
i 는 min,dp[i]=sigma dp[j],예 를 들 어 두 노드 모두 최대 치 를 얻 을 수 있 습 니 다.그러면 아무리 분배 하고 최소 치 를 취하 더 라 도 차 큰 값 이 어야 합 니 다.한 번 에 유추 하면 세 번 째 키 노드 가 있 으 면 결 과 는 세 번 째 로 큰 값 을 얻 을 수 있 습 니 다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
/**
* Created by dezhonger on 2019/4/14
*/
public class D {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
solver.solve(1, in, out);
out.close();
}
static class Task {
private int n;
private int[] m;
private int[] pa;
private List[] nodes;
//dp[i] ,1 ,2
private int[] dp;
public void solve(int testNumber, InputReader in, PrintWriter out) {
n = in.nextInt();
m = new int[n + 1];
pa = new int[n + 1];
dp = new int[n + 1];
for (int i = 1; i <= n; i++) m[i] = in.nextInt();
nodes = new List[n + 1];
for (int i = 1; i <= n; i++) nodes[i] = new ArrayList<>();
for (int i = 2; i <= n; i++) {
pa[i] = in.nextInt();
nodes[pa[i]].add(i);
}
int leafNumber = 0;
for (int i = 1; i <= n; i++) {
if (nodes[i].size() == 0) leafNumber++;
}
dfs(1);
System.out.println(leafNumber + 1 - dp[1]);
}
private void dfs(int nodeNumber) {
//
if (nodes[nodeNumber].size() == 0) {
//1
dp[nodeNumber] = 1;
return;
}
//1:max 0:min
for (int v : nodes[nodeNumber]) {
dfs(v);
}
if (m[nodeNumber] == 1) {
dp[nodeNumber] = Integer.MAX_VALUE;
for (int v : nodes[nodeNumber]) {
//
dp[nodeNumber] = Math.min(dp[nodeNumber], dp[v]);
}
} else {
dp[nodeNumber] = 0;
for (int v : nodes[nodeNumber]) {
dp[nodeNumber] += dp[v];
}
}
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.