-
-
Save meooow25/02097a3f73b7d1bff7fb9080c4af036c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// CLMTRO | |
// Tester: sarthakmanna | |
import java.io.*; | |
import java.util.*; | |
class CP { | |
public static void main(String[] args) throws Exception { | |
/*new Thread(null, new Runnable() { | |
@Override | |
public void run() { | |
try { | |
new Solver().solve(); | |
} catch (Exception e) { | |
e.printStackTrace(); | |
System.exit(1); | |
} | |
} | |
}, "Solver", 1l << 30).start();*/ | |
new Solver().solve(); | |
} | |
} | |
class Solver { | |
IO io = new IO(System.in, System.out); | |
final long INF = (long) 1e15 + 7; | |
int N; | |
long[] A, B; | |
long budget; | |
ArrayList<Integer>[] graph; | |
void solve() throws Exception { | |
int i, j, k; | |
for (int tc = io.nextInt(); tc > 0; --tc) { | |
N = io.nextInt(); budget = io.nextLong(); | |
A = new long[N]; | |
for (i = 0; i < N; ++i) A[i] = io.nextLong(); | |
B = new long[N]; | |
for (i = 0; i < N; ++i) B[i] = io.nextLong(); | |
graph = new ArrayList[N]; | |
for (i = 0; i < N; ++i) graph[i] = new ArrayList<>(); | |
for (i = 0; i < N - 1; ++i) { | |
int a = io.nextInt() - 1, b = io.nextInt() - 1; | |
graph[a].add(b); graph[b].add(a); | |
} | |
dpA = new long[N][]; // paint ith node with Ai | |
dpB = new long[N][]; // paint ith node with Bi | |
dpX = new long[N][]; // don't paint ith node | |
dfs(0, -7); | |
int ans = 0; | |
for (i = 0; i < N; ++i) for (j = 0; j < dpX[i].length; ++j) { | |
if (dpA[i][j] <= budget || dpB[i][j] <= budget || dpX[i][j] <= budget) | |
ans = Math.max(ans, j); | |
} | |
io.println(ans); | |
} | |
io.flush(); | |
} | |
long[][] dpA, dpB, dpX; | |
void dfs(int node, int par) { | |
dpA[node] = new long[2]; | |
dpB[node] = new long[2]; | |
dpX[node] = new long[2]; | |
dpA[node][0] = dpB[node][0] = dpX[node][0] = 0; | |
dpA[node][1] = A[node]; dpB[node][1] = dpX[node][1] = INF; | |
for (int child : graph[node]) if (child != par) { | |
dfs(child, node); | |
merge(child, node); | |
} | |
} | |
void merge(int ch, int par) { | |
int i, j, parLen = dpX[par].length, chLen = dpX[ch].length, newSize = parLen + chLen - 1; | |
long[] newDPa = new long[newSize]; Arrays.fill(newDPa, INF); | |
System.arraycopy(dpA[par], 0, newDPa, 0, parLen); | |
for (i = 1; i < parLen; ++i) for (j = 1; j < chLen; ++j) { | |
newDPa[i + j] = Math.min(newDPa[i + j], dpA[par][i] + dpX[ch][j]); | |
} | |
long[] newDPb = new long[newSize]; Arrays.fill(newDPb, INF); | |
System.arraycopy(dpB[par], 0, newDPb, 0, parLen); | |
for (i = 1; i < parLen; ++i) for (j = 1; j < chLen; ++j) { | |
newDPb[i + j] = Math.min(newDPb[i + j], | |
dpA[par][i] - A[par] + B[par] + dpA[ch][j] - A[ch] + B[ch]); | |
newDPb[i + j] = Math.min(newDPb[i + j], dpA[par][i] - A[par] + B[par] + dpB[ch][j]); | |
newDPb[i + j] = Math.min(newDPb[i + j], dpB[par][i] + dpA[ch][j] - A[ch] + B[ch]); | |
newDPb[i + j] = Math.min(newDPb[i + j], dpB[par][i] + dpB[ch][j]); | |
newDPb[i + j] = Math.min(newDPb[i + j], dpB[par][i] + dpX[ch][j]); | |
} | |
long[] newDPx = new long[newSize]; Arrays.fill(newDPx, INF); | |
System.arraycopy(dpX[par], 0, newDPx, 0, parLen); | |
for (i = 0; i < parLen; ++i) for (j = 0; j < chLen; ++j) { | |
newDPx[i + j] = Math.min(newDPx[i + j], dpX[par][i] + dpA[ch][j]); | |
newDPx[i + j] = Math.min(newDPx[i + j], dpX[par][i] + dpB[ch][j]); | |
newDPx[i + j] = Math.min(newDPx[i + j], dpX[par][i] + dpX[ch][j]); | |
} | |
dpA[par] = newDPa; dpB[par] = newDPb; dpX[par] = newDPx; | |
} | |
} | |
class IO { | |
static byte[] buf = new byte[2048]; | |
static int index, total; | |
static InputStream in; | |
static BufferedWriter bw; | |
IO(InputStream is, OutputStream os) { | |
try { | |
in = is; | |
bw = new BufferedWriter(new OutputStreamWriter(os)); | |
} catch (Exception e) { | |
} | |
} | |
IO(String inputFile, String outputFile) { | |
try { | |
in = new FileInputStream(inputFile); | |
bw = new BufferedWriter(new OutputStreamWriter( | |
new FileOutputStream(outputFile))); | |
} catch (Exception e) { | |
} | |
} | |
int scan() throws Exception { | |
if (index >= total) { | |
index = 0; | |
total = in.read(buf); | |
if (total <= 0) | |
return -1; | |
} | |
return buf[index++]; | |
} | |
String next() throws Exception { | |
int c; | |
for (c = scan(); c <= 32; c = scan()) ; | |
StringBuilder sb = new StringBuilder(); | |
for (; c > 32; c = scan()) | |
sb.append((char) c); | |
return sb.toString(); | |
} | |
int nextInt() throws Exception { | |
int c, val = 0; | |
for (c = scan(); c <= 32; c = scan()) ; | |
boolean neg = c == '-'; | |
if (c == '-' || c == '+') | |
c = scan(); | |
for (; c >= '0' && c <= '9'; c = scan()) | |
val = (val << 3) + (val << 1) + (c & 15); | |
return neg ? -val : val; | |
} | |
long nextLong() throws Exception { | |
int c; | |
long val = 0; | |
for (c = scan(); c <= 32; c = scan()) ; | |
boolean neg = c == '-'; | |
if (c == '-' || c == '+') | |
c = scan(); | |
for (; c >= '0' && c <= '9'; c = scan()) | |
val = (val << 3) + (val << 1) + (c & 15); | |
return neg ? -val : val; | |
} | |
void print(Object a) throws Exception { | |
bw.write(a.toString()); | |
} | |
void printsp(Object a) throws Exception { | |
print(a); | |
bw.write(" "); | |
} | |
void println() throws Exception { | |
bw.write("\n"); | |
} | |
void println(Object a) throws Exception { | |
print(a); | |
println(); | |
} | |
void flush() throws Exception { | |
bw.flush(); | |
bw.close(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment