当一次决策不是最优的时候,必须 rebuild。
当一次决策是最优的,但是同时还有其他最优的决策,可以 rebuild。
当一次决策是最优的,同时没有其他最优的决策,不能 rebuild。
因此建反图跑一遍最短路,由于边权为 $1$,bfs 即可。
```cpp
const int N = 2e5 + 7;
int n, m, k, v[N], a[N], d[N];
vi e[N], g[N];
queue<int> q;
int main() {
rd(n), rd(m);
for (int i = 1, x, y; i <= m; i++)
rd(x), rd(y), e[x].pb(y), g[y].pb(x);
rd(k), rda(a, k);
q.push(a[k]), v[a[k]] = 1;
while (q.size()) {
int x = q.front();
q.pop();
for (auto y : g[x])
if (!v[y]) q.push(y), d[y] = d[x] + 1, v[y] = 1;
}
int c1 = 0, c2 = 0;
for (int i = 1; i < k; i++) {
int x = a[i], y = a[i+1];
bool b1 = 0, b2 = 0;
for (auto z : e[x])
if (d[z] < d[y]) b1 = 1;
else if (y != z && d[z] == d[y]) b2 = 1;
if (b1) ++c1;
else if (b2) ++c2;
}
print(c1, ' '), print(c1 + c2);
return 0;
}
```