Check this editorial : - YouTube
WHY K IS always 1 .in every solution -x use.it mean k is always 1.
can anybody tell me why im getting wrong answer
/* package codechef; // don’t place package name! */
import java.io.;
import java.util.;
/* Name of the class has to be “Main” only if the class is public. */
class Temp {
static int cost;
static class Node {
int vertex, value;
public Node(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
}
static class Graph {
private int v;
private ArrayList<Node>[] adjList;
private boolean[] visited;
Graph(int v) {
this.v = v;
adjList = new ArrayList[v + 1];
for (int i = 1; i <= v; i++) {
adjList[i] = new ArrayList<>();
}
}
void addEdge(int u, Node node) {
adjList[u].add(node);
}
long dfs(Node root) {
visited = new boolean[v + 1];
return dfsHelper(root);
}
long dfsHelper(Node node) {
visited[node.vertex] = true;
long total_profit = 0;
for (Node neigbour : adjList[node.vertex]) {
if (!visited[neigbour.vertex]) {
total_profit += dfsHelper(neigbour);
}
}
return Math.max(total_profit + node.value, -cost);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
while (t-- > 0) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
cost = Integer.parseInt(st.nextToken());
int[] a = new int[n+1];
Graph g = new Graph(n);
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
int u, v;
for (int i = 1; i < n; i++) {
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
g.addEdge(u , new Node(v , a[v]));
}
sb.append(g.dfs(new Node(1, a[1])) + "\n");
}
System.out.println(sb);
}
}
As a beginner , I spent more than a day for this question. In the end I figured it all out and wanted to tell where I was stuck . I was really confused about the terms being compared there max(A[i] + res, -X) . They were being compared for the cost they would contribute in the maximum profit.
Let’s say performing the dfs you reach to the leaf node and now at this point you would want to whether keep the node(k =0) or delete the node(k > 0) . let’s say the leaf node is 3 . we check which one is better (keeping the node or deleting it) . 3’s value is -10, and -10 < -5(this is -X ) . we’re better off if we delete(k becomes 1) the node . so when we delete it . It’ll contribute to the max profit . And someone might think why aren’t we using k’s value as described in the formula . You just need to see and analyze them, It’s just that -X’s value is being added to the res(which means -X is being multiplied) , whenever we delete the node .
1 Like
Really Loved the editorial .thanks codechef