#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const int L_SZ = 1000;
const int MOD = 12;
static int dp[MAXN][MOD][2];
static vector<int> grafo[MAXN];
static int N,lastPtr,e1[MAXN],e2[MAXN],custo[MAXN];
static int resposta[MAXN],pai[MAXN],especial[MAXN],ini[MAXN],fim[MAXN],nivel[MAXN];
static void dfs_build(int v,int p){
for(int i : grafo[v]){
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
if(u == p) continue;
nivel[u] = nivel[v] + 1;
pai[u] = i;
dfs_build(u,v);
}
}
static void dfs_calculate(int v,int p,int dist){
if(especial[v]){
for(int i = ini[v], j = 0;i <= fim[v];i++,j++){
if(dist & (1 << j)) resposta[i] = 1;
else resposta[i] = 0;
}
}
for(int i : grafo[v]){
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
if(u == p) continue;
dfs_calculate(u,v,dist + custo[i]);
}
}
static int solve(int v,int p,int depth,int cor){
if(dp[v][depth][cor] != -1) return dp[v][depth][cor];
int tot = cor;
for(int i : grafo[v]){
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
if(u == p) continue;
if(depth == 1){
tot += solve(u,v,0,1);
}
else{
tot += min(solve(u,v,depth+1,0), solve(u,v,0,1) );
}
}
return dp[v][depth][cor] = tot;
}
static void recover_dp(int v,int p,int depth,int cor){
if(cor == 1 && v != 0){
int tam = 0;
for(int i = 0;(1 << i) <= nivel[v];i++) tam = i + 1;
especial[v] = 1;
ini[v] = lastPtr;
fim[v] = lastPtr + tam - 1;
lastPtr += tam;
}
for(int i : grafo[v]){
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
if(u == p) continue;
if(depth == 11){
recover_dp(u,v,0,1);
}
else{
if(solve(u,v,depth+1,0) <= solve(u,v,0,1)) recover_dp(u,v,depth+1,0);
else recover_dp(u,v,0,1);
}
}
}
void InitAnya(int n , int A[] , int B[]) {
memset(dp,-1,sizeof(dp));
N = n;
for(int i = 0;i<N-1;i++){
grafo[A[i]].push_back(i);
grafo[B[i]].push_back(i);
e1[i] = A[i];
e2[i] = B[i];
}
lastPtr = N - 1;
dfs_build(0,-1);
solve(0,-1,1,0);
recover_dp(0,-1,1,0);
especial[0] = 0;
}
void Anya(int C[]){
for(int i = 0;i<1000;i++) resposta[i] = 0;
for(int i = 0;i<N-1;i++) custo[i] = C[i];
for(int i = 0;i<N-1;i++) resposta[i] = C[i];
dfs_calculate(0,-1,0);
for(int i = 0 ; i < 1000 ; i++) Save(i , resposta[i]);
}
#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const int L_SZ = 1000;
const int MOD = 12;
static int dp[MAXN][MOD][2];
static vector<int> grafo[MAXN];
static int N,lastPtr,e1[MAXN],e2[MAXN];
static int pai[MAXN],especial[MAXN],ini[MAXN],fim[MAXN],nivel[MAXN];
static void dfs_build(int v,int p){
for(int i : grafo[v]){
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
if(u == p) continue;
nivel[u] = nivel[v] + 1;
pai[u] = i;
dfs_build(u,v);
}
}
static int solve(int v,int p,int depth,int cor){
if(dp[v][depth][cor] != -1) return dp[v][depth][cor];
int tot = cor;
for(int i : grafo[v]){
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
if(u == p) continue;
if(depth == 1){
tot += solve(u,v,0,1);
}
else{
tot += min(solve(u,v,depth+1,0), solve(u,v,0,1) );
}
}
return dp[v][depth][cor] = tot;
}
static void recover_dp(int v,int p,int depth,int cor){
if(cor == 1 && v != 0){
int tam = 0;
for(int i = 0;(1 << i) <= nivel[v];i++) tam = i + 1;
especial[v] = 1;
ini[v] = lastPtr;
fim[v] = lastPtr + tam - 1;
lastPtr += tam;
}
for(int i : grafo[v]){
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
if(u == p) continue;
if(depth == 11){
recover_dp(u,v,0,1);
}
else{
if(solve(u,v,depth+1,0) <= solve(u,v,0,1)) recover_dp(u,v,depth+1,0);
else recover_dp(u,v,0,1);
}
}
}
static int doQuery(int v){
if(v == 0) return 0;
if(especial[v]){
int numero = 0;
for(int i = ini[v],j = 0;i <= fim[v];i++,j++){
if(Ask(i)) numero += (1 << j);
}
return numero;
}
else{
int i = pai[v];
int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
return Ask(i) + doQuery(u);
}
}
void InitBoris(int n , int A[] , int B[]) {
memset(dp,-1,sizeof(dp));
N = n;
for(int i = 0;i<N-1;i++){
grafo[A[i]].push_back(i);
grafo[B[i]].push_back(i);
e1[i] = A[i];
e2[i] = B[i];
}
lastPtr = N - 1;
dfs_build(0,-1);
solve(0,-1,1,0);
recover_dp(0,-1,1,0);
}
int Boris(int city) {
return doQuery(city);
}
