UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212776#3829. CPanjunnan081ms6776kbC++111.4kb2024-10-20 11:01:032024-10-20 12:43:02

answer

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

const int MAXN = 100010;
vector<int> tree[MAXN];
int n;

int dfs(int node, int parent) {
    // 用来计算当前节点的子树节点数量
    int size = 1;
    // Paths will be counted as we traverse
    int totalPaths = 0;

    // 遍历当前节点的所有子节点
    for (int child : tree[node]) {
        if (child != parent) {
            int childSize = dfs(child, node); // 计算子树的大小
            size += childSize; // 更新当前节点的子树大小
            totalPaths += childSize; // 增加路径的数量
        }
    }
    
    // Return the size of the subtree for this node
    return size;
}

int main() {
    cin >> n; // 读取节点数量
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y; // 读取每条边
        tree[x].push_back(y); // 建树,x为父节点
        tree[y].push_back(x); // y为子节点
    }
    
    // 计算每个节点所需路径的最小权重
    int totalPaths = 0;
    totalPaths = dfs(1, -1); // 从根节点(1)开始DFS,-1表示没有父节点
    
    // 权重是总路径数量减去1,因为从根到一个节点的路径是总路径-1
    int minVS = totalPaths - 1;
    cout << minVS << endl; // 输出最小的路径集权重

    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 3592kb

input:

5
3 1
1 5
2 4
5 4

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

5
5 1
1 4
4 2
2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: -10
Wrong Answer
time: 0ms
memory: 3592kb

input:

5
4 5
4 3
4 1
4 2

output:

4

result:

wrong answer 1st numbers differ - expected: '6', found: '4'

Subtask #2:

score: 0
Wrong Answer

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 3596kb

input:

100
63 38
17 33
44 12
9 66
21 98
2 49
68 67
75 42
78 25
92 6
67 17
90 19
48 51
83 9
20 94
68 4
64 58...

output:

99

result:

wrong answer 1st numbers differ - expected: '167', found: '99'

Subtask #3:

score: 0
Wrong Answer

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 3628kb

input:

1000
228 978
939 994
911 13
8 806
680 958
779 832
673 924
627 806
354 476
320 218
766 848
171 944
90...

output:

999

result:

wrong answer 1st numbers differ - expected: '1893', found: '999'

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 81ms
memory: 6776kb

input:

100000
44881 88880
79640 18741
56510 31493
27649 50461
7015 98523
26337 91384
17594 52397
37312 3409...

output:

99999

result:

wrong answer 1st numbers differ - expected: '199052', found: '99999'

Subtask #5:

score: 0
Runtime Error

Test #22:

score: 0
Runtime Error

input:

1000000
198444 939986
569807 470692
847908 557044
739959 80274
772656 222835
832266 382872
267873 10...

output:


result: