社区讨论
谁能告诉我我的代码问题在哪?
P6086【模板】Prüfer(Prufer) 序列参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mm4l1scv
- 此快照首次捕获于
- 2026/02/27 15:40 2 周前
- 此快照最后确认于
- 2026/03/01 10:35 上周
CPP
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e6 + 5;
int n, m;
long long ans;
int fa[N], p[N], d[N];
long long TP() {
for (int i = 1; i < n; i ++) scanf("%d", &fa[i]), ++ d[fa[i]];
for (int i = 1, j = 1; i <= n - 2; i ++, j ++) {
while (d[j]) j ++;
p[i] = fa[j];
while (i <= n - 2 && !--d[p[i]] && p[i] < j) {
p[i + 1] = fa[p[i]];
i ++;
}
}
for (int i = 1; i <= n - 2; i ++) ans ^= 1LL * i * p[i];
return ans;
}
long long PT() {
for (int i = 1; i <= n - 2; i ++) scanf("%d", &p[i]), ++ d[p[i]];
p[n - 1] = n;
for (int i = 1, j = 1; i < n; i ++, j ++) {
while (d[j]) j ++;
fa[j] = p[i];
while (i < n && !--d[fa[j]] && p[i] < j) {
fa[p[i]] = p[i + 1];
i ++;
}
}
for (int i = 1; i < n; i ++) ans ^= 1LL * i * fa[i];
return ans;
}
int main() {
scanf("%d %d", &n, &m);
printf("%lld\n", (m == 1 ? TP() : PT()));
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...