Codeforces贿赂问题：超时代码优化与高效解法求助

存在N个城镇（编号1至N），由N-1条道路相连（1≤N≤10^5）。部分道路为单向，但可通过支付贿赂（初始金额为1美元）逆向非法通行，且每次逆向通行同一条道路后，下次的贿赂金额会翻倍。
司机从城镇1出发，需按给定顺序完成K次停靠（1≤K≤10^{6）。给定停靠点序列与道路信息，计算所需的最小贿赂金额，结果对10}9+7取模。

该问题为Codeforces的Bribe问题，暴力或贪心思路并不适用。我当前实现的代码在处理100000个城镇时被判定超时，我认为Dijkstra算法本身是高效的，但可能代码中存在其他复杂度较高的部分。请问如何优化我的代码，使其能在1秒内完成计算？

• 第一行输入N，表示城镇数量。
• 接下来N-1行每行输入三元组(a,b,x)，其中a、b为道路连接的城镇编号，x为0或1：0表示道路双向通行，1表示仅允许a→b方向合法通行。
• 下一行输入K，表示停靠次数。
• 最后一行输入K个正整数s₁,…,s_K，表示需访问的城镇序列。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int towns = scanner.nextInt();
        Graph g = new Graph(towns);
        for (int i = 0; i < towns-1; i++) {
            scanner.nextLine();
            int a =scanner.nextInt();
            int b =scanner.nextInt();
            int birection =scanner.nextInt();
            if(birection==0){
                g.addEdge(a-1,b-1,0);
                g.addEdge(b-1,a-1,0);

            }else{
                g.addEdge(a-1,b-1,0);
                g.addEdge(b-1,a-1,1);
            }

        }
        scanner.nextLine();
        int stops = scanner.nextInt();
        scanner.nextLine();
        int[] cities = new int[stops];
        for (int i = 0; i < cities.length; i++) {
            cities[i] = scanner.nextInt()-1;
        }
        scanner.close();
       //( g.print();
       /* for (int i = 0; i < cities.length; i++) {
            System.out.print(cities[i]+" ");

        }*/int stop=0;
        int j=0;
       //g.dfs(0,-1,2);
       // g.modDijkstra(3,4);
        for (int i = 0; i < cities.length; i++) {
            int endCity = cities[i];
            g.modDijkstra(j, endCity);
          //  System.out.println("Miasto 1 i 2: " + j + " " + endCity);
            j = endCity;
           // System.out.println(" ");
        }
        System.out.println(g.bribe);

    }

}


class Graph {
    ArrayList<ArrayList<Para>> aL;
    boolean[] visited;
    ArrayList dp;
     int polaczenia=0;
     int bribe=0;
    Graph(int size){
        aL = new ArrayList<>();
        visited =new boolean[size];
        dp = new ArrayList();

        for (int i = 0; i < size; i++) {
            aL.add(new ArrayList<>());
        }
    }
    public void addEdge(int v, int w,int b){
        aL.get(v).add(new Para(w,b));
      //  System.out.println("dodaje zaleznosc "+(v)+" do o wadze "+w+" "+b);
    }

    public void modDijkstra(int cur,int stop){
        if(cur==stop){
            return;
        }

        PriorityQueue<Para> pq = new PriorityQueue<>(aL.size(),Comparator.comparingInt(o->o.left));
        int[] distance = new int[aL.size()];
        Arrays.fill(distance,Integer.MAX_VALUE);
        pq.add(new Para(0,cur));
        distance[cur] = 0;
        while (!pq.isEmpty()){
            int node =pq.poll().getRight();
            for(Para p:aL.get(node)){
                if(distance[p.left]>distance[node]+p.getRight()){
                    distance[p.left]=distance[node]+p.getRight();
                    if(p.right!=0){
                        bribe+=p.getRight();
                        p.setRight(p.getRight()+1);

                    }
                    pq.add(new Para(distance[p.left],p.left));
                }
            }


        }

 
    }


}
class Para{
    int left;
    int right;
    Para(int l, int r){
        this.left = l;
        this.right= r;
    }

}

你的代码超时的核心原因是重复调用Dijkstra的次数过多（K可达1e6），加上错误的代价计算逻辑、低效的输入处理，直接导致时间复杂度爆炸。以下是针对性的优化方案：

核心问题分析 #

1. 时间复杂度超标：每次Dijkstra的复杂度是O(M + N logN)，K=1e6时总复杂度为O(K*(M+N logN))，完全无法通过。
2. 代价计算错误：你直接修改边权并累加，但逆向通行的代价是2^(次数-1)，而非简单递增，普通Dijkstra无法处理这种动态变化的边权。
3. 输入效率低下：Scanner处理1e6级别的输入速度过慢。

优化思路 #

利用题目中树结构（N个节点N-1条边）的特性，结合LCA（最近公共祖先）快速计算路径，统计每条逆向边的使用次数，再通过数学公式计算总贿赂：

• 每条逆向边被使用t次时，总代价为2^t - 1（等比数列求和：1+2+4+...+2^(t-1) = 2^t -1）。
• 预处理LCA和幂次数组，将每次路径查询的复杂度降至O(logN)，总复杂度控制在O(N logN + K logN)。

具体优化步骤 #

1. 替换输入方式 #

用BufferedReader+StringTokenizer替代Scanner，大幅提升输入速度：

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());

2. 预处理树与LCA #

• 构建树时标记每条边是否为逆向边（即从子节点到父节点需要贿赂）。
• 用倍增法预处理LCA的倍增数组，时间复杂度O(N logN)：

static final int LOG = 20;
int[] depth;
int[][] up;
boolean[] isReverse; // 标记节点到父节点的边是否需要贿赂

private void dfs(int u, int parent) {
    depth[u] = depth[parent] + 1;
    up[0][u] = parent;
    for (int i = 1; i < LOG; i++) {
        up[i][u] = up[i-1][up[i-1][u]];
    }
    for (Edge e : adj[u]) {
        if (e.to != parent) {
            isReverse[e.to] = e.isReverse;
            dfs(e.to, u);
        }
    }
}

private int getLCA(int u, int v) {
    if (depth[u] < depth[v]) {
        int temp = u;
        u = v;
        v = temp;
    }
    // 把u提到和v同一深度
    for (int i = LOG-1; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = up[i][u];
        }
    }
    if (u == v) return u;
    // 同时向上跳
    for (int i = LOG-1; i >= 0; i--) {
        if (up[i][u] != up[i][v]) {
            u = up[i][u];
            v = up[i][v];
        }
    }
    return up[0][u];
}

3. 统计逆向边使用次数 #

对于停靠序列中的连续节点u→v，通过LCA分解路径为u→LCA和v→LCA，统计路径上的逆向边次数：

long[] cnt = new long[N+1]; // 每条逆向边的使用次数

private void countReverse(int u, int lca) {
    while (u != lca) {
        if (isReverse[u]) {
            cnt[u]++;
        }
        u = up[0][u];
    }
}

// 处理停靠序列
int prev = 1; // 从城镇1出发
for (int s : stops) {
    int lca = getLCA(prev, s);
    countReverse(prev, lca);
    countReverse(s, lca);
    prev = s;
}

4. 预处理幂次计算总贿赂 #

提前计算2^0到2^K的模值，避免重复计算：

static final int MOD = 1_000_000_007;
long[] pow2 = new long[1_000_001];

private void precomputePow() {
    pow2[0] = 1;
    for (int i = 1; i <= 1_000_000; i++) {
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
}

// 计算总贿赂
long total = 0;
for (int i = 1; i <= N; i++) {
    if (cnt[i] > 0) {
        total = (total + (pow2[(int)cnt[i]] - 1 + MOD) % MOD) % MOD;
    }
}
System.out.println(total);

内容的提问来源于stack exchange，提问作者Marek