Skip to content

Instantly share code, notes, and snippets.

@meooow25
Created February 26, 2019 04:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save meooow25/02097a3f73b7d1bff7fb9080c4af036c to your computer and use it in GitHub Desktop.
Save meooow25/02097a3f73b7d1bff7fb9080c4af036c to your computer and use it in GitHub Desktop.
// 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