QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#318129#6958. Equivalenceluyiming123AC ✓757ms130808kbC++231.6kb2024-01-30 16:11:492024-01-30 16:11:49

Judging History

你现在查看的是最新测评结果

  • [2024-01-30 16:11:49]
  • 评测
  • 测评结果:AC
  • 用时:757ms
  • 内存:130808kb
  • [2024-01-30 16:11:49]
  • 提交

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