Мы дали дерево (N узлов) и каждому узлу дерева присвоили номер. Нам нужно найти наибольшую сумму, которую мы можем получить, пройдя путь в этом дереве так, чтобы у каждого узла в пути было одинаковое количество установленных битов.
Учитывая, массив A, где A [i] обозначает значение, данное i-му Узлу; Даны два массива, B и C, где i-й элемент представляет i-й край, соединяющий узлы B [i] с C [i].
Ввод: A: 16 1 7 16 2 3 2 B: 1 1 1 4 4 6 C: 2 3 4 5 6 7
Вывод: 35 (2-> 1-> 4-> 2)
Я пытался: Я создал список соседей, используя B и C. Кроме того, создан другой массив бит [n], где бит [i] представляет нет. установленного бита в узле ih. Затем, один за другим перебирая каждый узел (фиксируя его как начальный путь), и рекурсивно пытайтесь вычислить максимальную сумму.
int calpath(int A[], ArrayList<ArrayList<Integer>> al,int u,int bit[],int parent){
int ans=0;
int currbit=bit[u];
for(int i=0;i<al.get(u).size();i++){
int v = al.get(u).get(i);
if(parent!=v){
if(bit[v]==currbit){
ans = Math.max(calpath(A,al,v,bit,u),ans);
}
}
}
return (ans+A[u])%(1000000007);
}
//-----------------At main-----------------
for(int i=0;i<A.length;i++){
ans = Math.max(calpath(A,al,i,bit,-1),ans);
}
Это, однако, наивный способ решения вышеуказанной проблемы, но он все равно дает мне неправильный Ответ. В чем проблема с приведенным выше кодом? Есть ли лучший подход для решения этой проблемы?
Я не могу опубликовать ссылку на онлайн-судью по окончании теста.