import java.io.*;
import java.util.*;
public class Main{
static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StreamTokenizer st = new StreamTokenizer(buf);
public static int nextInt() throws IOException {
st.nextToken();
return (int) st.nval;
}
static int n, m, s, tot = 0, cnt = 0;
static int[] head,d,p;
static int[][] anc;
static Edge[] e;
static int ans = Integer.MIN_VALUE,ansNode=0;
static int[] size, f,weight;
static int center = 0;
public static void main(String[] args) throws IOException {
n=nextInt();
m=nextInt();
head = new int[n+1];
d = new int[n+1];
p = new int[n+1];
e = new Edge[2*n+1];
anc = new int[n+1][20];
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<=n-1;i++){
int a = nextInt(),b=nextInt();
add(a,b);
add(b,a);
}
d[1]=1;
dfs(1,0);
init();
for(int i=1;i<=m;i++){
int a=nextInt(),b=nextInt();
int lca = query(a,b);
// System.out.println(lca);
++p[a];++p[b];
--p[lca];--p[anc[lca][0]];
}
get(1,0);
System.out.println(ans);
// for(int i=1;i<=n;i++)
// System.out.print(p[i]+" ");
}
public static void get(int u,int fa){
for(int i=head[u];i!=-1;i=e[i].next){
int v = e[i].v;
if(v==fa) continue;
get(v,u);
p[u]+=p[v];
}
ans=Math.max(ans,p[u]);
}
public static int query(int u,int v){
if(d[u]<d[v]){
int temp = v;
v=u;
u=temp;
}
for(int i=18;i>=0;i--)
if(d[anc[u][i]]>=d[v])
u=anc[u][i];
if(u==v) return u;
for(int i=18;i>=0;i--){
if(anc[u][i]!=anc[v][i]){
u=anc[u][i];
v = anc[v][i];
}
}
return anc[u][0];
}
public static void dfs(int u,int fa){
for(int i=head[u];i!=-1;i=e[i].next){
int v = e[i].v;
if(v==fa) continue;
d[v] = d[u] + 1;
anc[v][0]=u;
dfs(v,u);
}
}
public static void init(){
for(int j=1;j<=18;j++)
for(int i=1;i<=n;i++)
anc[i][j]=anc[anc[i][j-1]][j-1];
}
public static void add(int u, int v) {
e[++cnt] = new Edge(v, head[u]);
head[u] = cnt;
}
static class Edge {
int v, next;
public Edge(int v, int next) {
this.v = v;
this.next = next;
}
}
}
第6个点和第14点RE了,其中第6个点的数据开头是这样子的
50000 100000
26268 13400
24250 49931
35998 39456
29749 3227
31447 34720
4090 2107
27602 3796
.......
明明数组e
大小是2*n+1
,但在本地跑时,总会在add()
函数中报错
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 29885 out of bounds for length 23214
at Main.add(Main.java:119)
at Main.main(Main.java:41)
感觉这个29885
和23214
来得莫名奇妙的
这是为啥