QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318129 | #6958. Equivalence | luyiming123 | AC ✓ | 757ms | 130808kb | C++23 | 1.6kb | 2024-01-30 16:11:49 | 2024-01-30 16:11:49 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, p1[N];
vector <pair<int, int> > g[N];
int d[N], fa[22][N], dep[N];
void dfs(int x, int fa)
{
dep[x] = dep[fa] + 1, ::fa[0][x] = fa;
for(int i = 1; i <= 20; i++) ::fa[i][x] = ::fa[i - 1][::fa[i - 1][x]];
for(auto [v, w] : g[x])
{
dfs(v, x);
}
return;
}
int LCA(int x, int y)
{
if(dep[x] > dep[y]) swap(x, y);
for(int i = 20; i >= 0; i--)
if(dep[x] + (1 << i) <= dep[y]) y = fa[i][y];
if(x == y) return x;
for(int i = 20; i >= 0; i--)
if(fa[i][x] != fa[i][y]) x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
int ans = 0;
void dfs2(int x, int fa)
{
for(auto [v, w] : g[x])
{
dfs2(v, x);
d[x] += d[v];
if(d[v] > 1 && w > 0) ++ans;
}
return;
}
int main(void)
{
int Test; scanf("%d", &Test);
while(Test--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) d[i] = 0, dep[i] = 0, g[i].clear();
for(int i = 2; i <= n; i++) scanf("%d", &p1[i]);
for(int i = 2; i <= n; i++)
{
int v; scanf("%d", &v);
g[p1[i]].push_back({i, v});
}
dfs(1, 0);
for(int i = 2; i <= n; i++)
{
int f; scanf("%d", &f);
// egde (f, i)
int lca = LCA(f, i);
// printf("(%d, %d), lca = %d\n", f, i, lca);
d[lca] -= 2, d[f]++, d[i]++;
}
ans = 0;
dfs2(1, 0);
printf("%d\n", ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 757ms
memory: 130808kb
input:
8514 265000 72963 99588 118133 209949 249723 133275 171942 167920 86420 191069 169911 123458 176051 140795 122013 123039 252726 229192 52056 65706 247786 155474 231748 50060 24682 114313 43549 53896 73048 149564 51333 62885 117376 255302 235170 95044 56347 246767 193580 219540 227757 92735 173157 17...
output:
75123 27033 26721 233600 1082 1079 1077 1131 1055 1052 1026 1075 1013 1144 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0...
result:
ok 8514 lines