QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770789#9751. 覆盖一棵树liuhuahua#WA 15ms8696kbC++14631b2024-11-22 00:13:342024-11-22 00:13:42

Judging History

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

  • [2024-11-22 00:13:42]
  • 评测
  • 测评结果：WA
  • 用时：15ms
  • 内存：8696kb
查看
  • [2024-11-22 00:13:34]
  • 提交

answer

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int T,n,dp[N],ans;
vector<int>b[N];
void dfs(int x){
    dp[x]=-1;
    if(!b[x].size()){
        dp[x]=0;
        return;
    }
    for(auto y:b[x]){
        dfs(y);
        if(dp[x]==-1||dp[y]+1<dp[x])dp[x]=dp[y]+1;
    }
    if(x!=1)ans=max(ans,dp[x]+1);
}
int main(){
    cin>>T;
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)b[i].clear();
        for(int i=2;i<=n;i++){
            int p;
            scanf("%d",&p);
            b[p].push_back(i);
        }ans=0;
        dfs(1);
        cout<<ans<<"\n";
    }
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8696kb

input:

2
8
1 2 3 2 5 1 7
8
1 2 3 4 5 6 7

output:

3
7

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 15ms
memory: 8284kb

input:

33428
10
1 2 3 3 4 6 7 7 9
10
1 2 3 4 5 6 7 8 8
8
1 2 3 4 5 6 7
8
1 2 3 4 4 6 7
4
1 2 3
3
1 2
3
1 1
9
1 2 3 4 5 6 7 8
2
1
3
1 2
10
1 2 3 4 5 6 7 8 9
3
1 2
2
1
10
1 2 3 4 5 6 7 8 9
2
1
5
1 2 2 4
8
1 2 3 4 5 6 7
5
1 2 3 3
2
1
5
1 2 3 4
3
1 2
9
1 2 3 4 5 6 6 8
9
1 2 3 4 5 6 7 8
9
1 2 3 4 5 5 7 8
8
1 2 ...

output:

4
8
7
4
3
2
0
8
0
2
9
2
0
9
0
2
7
3
0
4
2
6
8
5
6
4
0
2
9
7
4
3
4
5
7
3
3
7
3
4
9
3
3
3
8
2
8
6
2
4
6
4
2
0
5
2
5
2
2
4
2
2
5
2
2
6
3
9
2
5
5
3
2
2
0
2
0
9
0
5
0
6
3
5
2
9
4
2
3
0
3
3
0
2
5
3
8
4
7
6
4
6
4
6
8
4
4
2
4
5
0
7
7
5
2
2
2
2
7
3
3
6
4
3
3
3
2
2
4
8
4
5
8
6
4
2
3
7
6
0
3
2
7
7
9
0
2
5
5
2
...

result:

wrong answer 7th lines differ - expected: '1', found: '0'
English 繁體中文 简体中文

伺服器時間: 2025-01-21 06:00:44 | 開源專案