#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define INF INT_MAX
int n, a[N], to[N], root;
int f[N][0], vis[N];
vector<int> g[N];
void dfs(int u) {
f[u][0] = f[u][1] = 0;
vis[u] = 1;
int k = -INF;
if (!g[u].size() || g[u][0] == root) k = 0;
for (auto v : g[u]) {
if (vis[v]) continue;
dfs(v);
int t = max(f[v][0], f[v][1]);
cout << f[v][0] << " ";
f[u][0] += t;
cout << f[v][0] << "\n";
k = max(k, f[v][0] - t);
}
f[u][1] = f[u][0] + 1 + k;
return;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
g[a[i]].push_back(i);
}
for (int i = 1; i <= n; i++)
if (!vis[i]) {
root = i;
dfs(i);
}
return 0;
}
代码是这样的，未写完，不过可以看到我在dfs中的调试语句。
如果我使用这组样例。
9
8 1 2 2 1 5 6 6 3
则调试会输出
0 1
1 3
0 1
1 4
0 1
0 1
1 3
3 8
也就是说，在
cout << f[v][0] << " ";
f[u][0] += t;
cout << f[v][0] << "\n";
中，中间的代码导致了 f_{v,0} 的变化。
不知道怎么回事。