Luobuyu's Blog

0%

2581. 统计可能的树根数目

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.2k 阅读时长 ≈ 2 分钟
换根dp，需要注意一下猜测节点对。

2581.统计可能的树根数目

题目描述：

Alice 有一棵 n 个节点的树，节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] ，表示树中节点 ai 和 bi 之间有一条边。

Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次 猜测 。每一次猜测，Bob 做如下事情：

  • 选择两个 不相等 的整数 u 和 v ，且树中必须存在边 [u, v] 。
  • Bob 猜测树中 u 是 v 的 父节点 。

Bob 的猜测用二维整数数组 guesses 表示，其中 guesses[j] = [uj, vj] 表示 Bob 猜 uj 是 vj 的父节点。

Alice 非常懒，她不想逐个回答 Bob 的猜测，只告诉 Bob 这些猜测里面 至少 有 k 个猜测的结果为 true 。

给你二维整数数组 edges ，Bob 的所有猜测和整数 k ，请你返回可能成为树根的 节点数目 。如果没有这样的树，则返回 0。

数据范围：

$2\le n \le 10^5, 1\le guesses.len \le 10^5$

$guesses$ 是唯一的。

题解：

很明显需要换根dp，首先处理出根节点 $0$ 满足多少个猜测，然后再次 $dfs$ 换根，求出每个节点作为根满足的猜测数量。

主要是需要处理父子节点对 $u \rightarrow v$ 出现转换 $v \rightarrow u$ 后，答案是如何变化的。

首先可以先 $ans[v] = ans[u]$ 然后分析父子关系互换之后答案的变化，如果存在猜测 $u\rightarrow v$ ，那么互换之后 $ans[v] -1 $ ，如果存在 $v\rightarrow u$ ，那么互换之后 $ans[v] + 1$ 。

先使用一个 $dfs1$ 求出 $0$ 作为根节点时的答案，然后再使用 $dfs2$ 换根，更新其他节点作为根时的答案。

需要注意的是，需要使用 $set$ 存所有的猜测对，但是 $n$ 的范围大概到 $2^{20}$ ，可以使用 $(1ll \times u << 32) | v$ ，需要转化为 long long，然后左移 $32$ 位，再或上另一个点。

代码：

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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    vector<vector<int>> g;
    vector<int> ans;
    unordered_set<long long> s;
    bool count(long long u, long long v)
    {
        return s.count((u << 32) | v);
    }
    void insert(long long u, long long v)
    {
        s.insert((u << 32) | v);
    }

    void dfs1(int u, int fa)
    {
        // unordered_set<int> son;
        for (int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i];
            if (v == fa)
                continue;
            if (count(u, v))
                ++ans[0];
            dfs1(v, u);
        }
    }
    void dfs2(int u, int fa)
    {
        for (int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i];
            if (v == fa)
                continue;
            ans[v] = ans[u];
            if (count(u, v))
                ans[v]--;
            if (count(v, u))
                ans[v]++;
            dfs2(v, u);
        }
    }
    int rootCount(vector<vector<int>> &edges, vector<vector<int>> &guesses, int k)
    {
        int n = edges.size() + 1;
        g.resize(n);
        ans.resize(n);
        for (auto &edge : edges)
        {
            int u = edge[0], v = edge[1];
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        for (auto &edge : guesses)
        {
            int u = edge[0], v = edge[1];
            insert(u, v);
        }
        // 先假设 0 为根，遍历一遍，找到几个为 true 的
        dfs1(0, -1);
        dfs2(0, -1);
        int cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            if (ans[i] >= k)
                ++cnt;
        }
        return cnt;
    }
};