CF1794E E. Labeling the Tree with Distances题解

E. Labeling the Tree with Distances

题目翻译

​ 题目给我们一个n个节点的树，还有n - 1个标签，我们还可以自由挑选一个任意数值的标签，当以某个节点为根时，树中每个节点的到根节点的距离能与n个标签一一对应，那么我们就称这个作为根节点的点为好点。我们需要求出所有的好点并按照升序输出。

思路

​ 首先我们可以想到对于某个节点为根的树维护所有节点到他的距离可以考虑换根dp，但是此时我们还是无法很好的考虑距离为x的节点的数量，并且我们无法快速的对n个标签，其中还有一个不确定的标签进行快速判断是否符合要求。

​ 我们重新思考我们的需求，我们需要判断一个数组每个元素的值的出现次数是否相同，我们发现这类似于字符串的一个个判断，考虑对这个数组进行类似进制哈希的做法，列入cnt0 * base0 + cnt1 * base1 + cnt2 * base2，这样的进制哈希我们也是可以换根dp来维护某个节点为根时所有到它距离的距离cnt的哈希数值的。同时我们注意到对于未确定的那个标签实际上只有n种可能，因为树的深度不超过n，所以我们可以每个都尝试一下，处理出哈希放到set里即可帮助我们快速判断。这实际上是一个线段树优化哈希，注意到本题的哈希值种类有1e5种，对哈希的强度有一定需求，可以使用多模值哈希或是直接放大哈希的值域范围，我代码里的做法手写了int128的乘法来将哈希的值域放大到了1e18，这样哈希冲突的概率极低，模数使用1e18 + 9，base使用随机生成的大进位数。

代码

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
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

constexpr ll mod = ((ll)1e18) + 9;

ll mul(ll a, ll b){
    return __int128(a) * b % mod;
}

void solve(){
    int n;
    std::cin >> n;
    ll base = rng() % 1000000000 + 234567;
    std::vector<int> cnt(n + 1, 0);
    std::vector<ll> p(n + 1, 1);
    for(int i = 1; i <= n; i++){
        p[i] = mul(p[i - 1], base);
    }

    for(int i = 1; i <= n - 1; i++){
        int x;
        std::cin >> x;
        if(x <= n)
            cnt[x] += 1;
    }
    std::vector<std::vector<int>> vec(n + 1);
    for(int i = 1; i <= n - 1; i++){
        int x, y;
        std::cin >> x >> y;
        vec[x].push_back(y);
        vec[y].push_back(x);
        //std::cerr << x << space << y << endl;
    }

    ll now = 0;
    for(int i = n; i >= 0; i--){
        now = mul(now, base);
        now += cnt[i];
    }
    std::set<ll> win;
    for(int i = n; i >= 0; i--){
        ll res = p[i];
        win.insert((res + now) % mod);
    }


    std::vector<ll> hash(n + 1, 0);
    std::function<void(int, int, int)> dfs1 = [&](int node, int fa, int dep){
        hash[node] = 1;
        for(auto v : vec[node]){
            if(v != fa){
                dfs1(v, node, dep + 1);
                hash[node] = (mul(hash[v], base) + hash[node]) % mod;
            }
        }
    };
    dfs1(1, -1, 0);

    std::vector<int> ans;
    std::function<void(int, int, ll)> dfs2 = [&](int node, int fa, ll hashnow) -> void{
        if(win.count(hashnow)){
            ans.push_back(node);
        }
        for(auto v : vec[node]){
            if(v != fa){
                ll hashto = (hashnow - mul(hash[v], base)) % mod;
                hashto = (hashto + mod) % mod;
                hashto = mul(hashto, base);
                hashto = (hashto + hash[v]) % mod;
                dfs2(v, node, hashto);
            }
        }
    };
    dfs2(1, -1, hash[1]);
    std::cout << ans.size() << endl;
    std::sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++)
        std::cout << ans[i] << sendl[i == ans.size() - 1];
}