Java代码求助,86分,有两个点RE了
查看原帖
Java代码求助,86分,有两个点RE了
60925
KKKZOZ楼主2022/12/3 16:34
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)

感觉这个2988523214来得莫名奇妙的

这是为啥

2022/12/3 16:34
加载中...