考虑以下问题：
有 N 个城镇（编号为 1 到 N）和连接它们的 N - 1 条道路（其中 1 <= N <= 10^5). Some of these roads are unidirectional, but may be traversed illegally in the opposite direction by paying a bribe (starting at $1). After traversing a road in the wrong direction, the bribe required for the next time traversing the same road in the wrong direction doubles.
司机从城镇 1 出发，必须经过 K 站（其中 1 <= K <= 10^6) in the order that these stops are given. Given these stops, and the description of the roads, calculate the minimum amount of money required for bribes, modulo 10^9 + 7.
帮助我编写代码，因为对于 100.000 个城镇，codeforces 说：时间限制。我认为这个 dijkstra 是有效的，但也许还有其他地方可能有它的第二次或第三次幂。 我可以在我的代码中改进什么。 预先感谢！
这是一个代码强制问题，贿赂、暴力或其他贪婪我认为不是一个好主意。
输入 第一行包含 N，即鲁里塔尼亚的城镇数量。以下 N - 1 行包含有关城镇之间的各个道路的信息。道路由整数元组 (a,b,x) 表示，它们之间用单个空格字符分隔。数字a和b代表该特定道路连接的城市，x为0或1：0表示该道路是双向的，1表示仅a → b方向是合法的。下一行包含 K，即博尔纳必须停靠的次数。输入的最后一行包含 K 个正整数 s1, …, sK：Borna 必须访问的城镇。
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 算法。请注意，该图是一棵树，这意味着两个节点之间的最短路径始终是从一个节点到最低公共祖先的路径与从 LCA 到另一个节点的路径的组合。我们可以任意给树取根而不影响答案。
对于这个问题，我们需要统计driver从每个节点向上移动到每个节点的次数。每条路径的这些更新可以通过树上的差异数组在恒定时间内完成。处理完所有的停靠点后，我们可以将差异数组中的所有变化从子节点推送到父节点，以累加每个方向的实际遍历次数。
然后，我们可以找到每条单向道路的错误方向通过的次数。贿赂的成本将为 2^0 + 2^1 + ... + 2^(count - 1)（由于每次价格加倍）。这显然是一个等比数列，其总和为 2^count - 1。我们可以通过二进制求幂或通过预先计算从
0K总时间复杂度：
O(N log N + K log N + N log K)示例实现：
private static final int MOD = 1000000007;
private static List<Integer>[] adj;
private static int[] depth, pathup, pathdown;
private static int maxLog;
private static int[][] ancestor;
public static void main(String[] args) throws IOException {
class Road {
int from, to;
Road(int from, int to) {
this.from = from;
this.to = to;
}
}
var oneWay = new ArrayList<Road>();
try (var br = new BufferedReader(new InputStreamReader(System.in))) {
int towns = Integer.parseInt(br.readLine());
adj = new List[towns + 1];
for (int i = 1; i <= towns; i++)
adj[i] = new ArrayList<>();
depth = new int[towns + 1];
pathup = new int[towns + 1];
pathdown = new int[towns + 1];
maxLog = 32 - Integer.numberOfLeadingZeros(towns - 1);
ancestor = new int[towns + 1][maxLog + 1];
for (int i = 1; i < towns; i++) {
var st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken()),
dir = Integer.parseInt(st.nextToken());
adj[a].add(b);
adj[b].add(a);
if (dir == 1) oneWay.add(new Road(a, b));
}
DFS(1, 0);
int stops = Integer.parseInt(br.readLine()), prevLoc = 1;
var st = new StringTokenizer(br.readLine());
for (int i = 0; i < stops; i++) {
int stop = Integer.parseInt(st.nextToken()), lca = LCA(prevLoc, stop);
prevLoc = stop;
++pathup[prevLoc];
++pathdown[stop];
--pathup[lca];
--pathdown[lca];
}
pushUp(1, 0);
long bribe = 0;
for (var road : oneWay) {
int wrongWayUses = depth[road.from] < depth[road.to] ? pathup[road.to] : pathdown[road.from];
long total = 1, square = 2;
while (wrongWayUses > 0) {
if ((wrongWayUses & 1) == 1) total = total * square % MOD;
square = square * square % MOD;
wrongWayUses >>= 1;
}
bribe = (bribe + total - 1) % MOD;
}
System.out.println(bribe);
}
}
private static void DFS(int curr, int par) {
ancestor[curr][0] = par;
for (int i = 1; i <= maxLog; i++)
ancestor[curr][i] = ancestor[ancestor[curr][i - 1]][i - 1];
depth[curr] = depth[par] + 1;
for (int next : adj[curr])
if (next != par)
DFS(next, curr);
}
private static int LCA(int x, int y) {
if (depth[x] < depth[y]) return LCA(y, x);
for (int i = maxLog; i >= 0; i--)
if (depth[x] - (1 << i) >= depth[y]) x = ancestor[x][i];
if (x == y) return x;
for (int i = maxLog; i >= 0; i--)
if (ancestor[x][i] != ancestor[y][i]) {
x = ancestor[x][i];
y = ancestor[y][i];
}
return ancestor[y][0];
}
private static void pushUp(int curr, int par) {
for (int next : adj[curr])
if (next != par) {
pushUp(next, curr);
pathup[curr] += pathup[next];
pathdown[curr] += pathdown[next];
}
}