洛谷 P5018 【对称二叉树】

Solution
932 Words

本题考察选手对DFS及树结构的掌握程度

  • 首先，你把数据读入之后，先用一个大法师把以每个节点为根的子树的大小和权值都预处理出来，方便待会剪枝

  • 然后，你对以每个节点为根的子树，都判断一下以下条件（这时刚才处理的东西就有用了）

  • ① 左子树和右子树的节点数是否相等

  • ② 左子树和右子树的权值是否相等

  • ③ 以当前节点为根的子树大小是不是超过答案

  • 第三个很重要，不加（洛谷 数据）最后一个点会TLE

  • 有一个显而易见的剪枝：因为答案至少是1，所以大小为1的子树就不用check了，不然浪费常数

  • 然后就是暴力判了

  • 递归下去，建立两个队列，保存当前处理到的左子树上和右子树上的节点，判左子树当前节点的左儿子和右子树当前节点的右儿子权值是否相等，右子树当前节点的左儿子和左子树当前节点的右儿子权值是否相等（注意对应）

  • 还有判下对应的节点有没有一个是空的一个没空的情况

  • 如果不相等就返回

  • 相等的话就扔进队列（注意对应顺序！）

  • 注意：上述处理一定要左右子树一起做，不能先处理一边，再处理另一边，不然会WA

  • 到最后如果都可以的话就return true

  • 附考场代码

  • 不得不说，为了能过，我加了一堆卡常
  • 3e6的输入规模应该还是要快读的吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# include <bits/stdc++.h>

# define R register 

const int MaxN = 1000010;

struct node//节点
{
    int val;
    int l, r;
};

node a[MaxN];
int f[MaxN], val[MaxN], ind[MaxN];//f[i]表示以i为根的子树大小，val表示以i为根的子树权值和，ind没啥用

inline void read(int &x)//快读
{
    x = 0;
    bool op = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0')
    {
        if(ch == '-')
            op = 0;
        ch = getchar();
    }
    while(ch <= '9' && ch >= '0')
        x = (x << 1) + (x << 3) + (ch - '0'), ch = getchar();
    if(!op)
        x = -x;
}

void dfs(int root)
{
    if(root == -1)
        return;
    if(a[root].l == -1 && a[root].r == -1)
        f[root] = 1, val[root] = a[root].val;
    else
    {
        dfs(a[root].l);
        dfs(a[root].r);
        f[root] = f[a[root].l] + f[a[root].r] + 1;
        val[root] = val[a[root].l] + val[a[root].r] + a[root].val;
    }

}

inline int check(int x)
{
    std::queue<int> l, r;
    l.push(x), r.push(x);
    while(!l.empty() || !r.empty())
    {
        if(l.empty() || r.empty())
            return false;//一边空了，一边没空
        R int lx = l.front(), rx = r.front();
        l.pop(), r.pop();
        if(a[lx].val != a[rx].val)
            return false;
        R int lson[3], rson[3];
        lson[1] = a[lx].l, lson[2] = a[lx].r;//左子树当前节点的左儿子,左子树当前节点的右儿子
        rson[1] = a[rx].l, rson[2] = a[rx].r;//右子树当前节点的左儿子,右子树当前节点的右儿子
        if((lson[1] == -1 && rson[2] != -1) || (lson[1] != -1 && rson[2] == -1))
            return false;//一边空了，一边没空
        if((lson[2] == -1 && rson[1] != -1) || (lson[2] != -1 && rson[1] == -1))
            return false;//一边空了，一边没空
        if(lson[1] != -1)
            l.push(lson[1]);
        if(lson[2] != -1)
            l.push(lson[2]);
        if(rson[2] != -1)
            r.push(rson[2]);
        if(rson[1] != -1)
            r.push(rson[1]);
        //推进队列
    }
    return true;
}

int main()
{
// 	freopen("tree.in", "r", stdin);
// 	freopen("tree.out", "w", stdout);
    R int n;
    scanf("%d", &n);
    for(R unsigned i = 1; i <= n; ++i)
        read(a[i].val);
    for(R unsigned i = 1; i <= n; ++i)
        read(a[i].l), read(a[i].r), ++ind[a[i].l], ++ind[a[i].r];//处理入度
    R unsigned root;
    for(R unsigned i = 1; i <= n; ++i)
    {
        if(!ind[i])
        {
            root = i;
            break;
        }
    }//找树根
    dfs(root);//预处理
    int ans = 1;
    for(R unsigned i = 1; i <= n; ++i)//枚举子树
    {
        if(f[a[i].l] != f[a[i].r])
            continue;//剪枝1
        if(val[a[i].l] != val[a[i].r])
            continue;//剪枝2
        if(f[i] < ans || f[i] == 1)
            continue;//剪枝3
        if(check(i))
            ans = f[i];//更新答案
    }
    printf("%d", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
DFS, 树
CF1063B 【Labyrinth】
CF550A 【Two Substrings】
关注我

分类

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×