Skip to content

S2OJ - 1497. 树

题解802 字
# S2OJ # 树 # 随机化
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

有一棵大小为 NN 的树，树上每条边有一个数字，有 MM 次询问，每次询问一对 (x,y)(x, y)，你需要回答从 xx 到 yy 的路径的数字任意排列是否能构成一个回文的序列，求 MM 次询问中结果为是的次数。

#输入格式

第一行为两个整数 N,MN, M，代表序列的长度和询问的个数。

接下来 N−1N - 1 行：每行三个数字 ui,vi,wiu_i, v_i, w_i，描述一条边 (ui,vi)(u_i, v_i) 与边上的字符 wiw_i。

接下来一行：A1A_1, B1B_1。

MM 个询问如以下方式生成：

  • xi=Ai mod n+1x_i = A_i \bmod n + 1；
  • yi=Bi mod n+1y_i = B_i \bmod n + 1；
  • Ai=Ai−1×666073 mod 1000000007A_i = A_{i - 1} \times 666073 \bmod 1000000007；
  • Bi=Bi−1×233 mod 998244353B_i = B_{i - 1} \times 233 \bmod 998244353。

#输出格式

一行一个数字，代表 MM 次询问中结果为是的次数。

#输入输出样例

样例输入 #1

4 1
1 2 1
2 3 1
1 4 2
3 4

样例输出 #1

1

#数据范围与约定

测试点编号 分值 约束
11 1010 N,M≤2000N, M \leq 2000
22 2323 N,M≤105N, M \leq 10^5，vi=ui+1v_i=u_i+1
33 1515 N,M≤105N, M \leq 10^5
44 N,M≤106N, M \leq 10^6，wi≤30w_i ≤ 30
55 1717 N,M≤106N, M \leq 10^6
66 2020 N≤106N \leq 10^6，M≤2×107M \leq 2 \times 10^7

对于 100%100\% 的数据，N≤106N \leq 10^6，M≤2×107M \leq 2 \times 10^7。

#思路

偶数个相同数的异或和为零。

可以为某种颜色设定一个特定的哈希值（随机即可），然后求出 x→yx \to y 路径上的哈希值的异或和。

如果这条路径的长度为偶数，那么其异或和应为 00，否则应为路径上某一条边的颜色的哈希值。符合上述条件之一者，该路径是回文路径。

提示

本题的随机数应在 unsigned long long 范围内取值。

#代码

C++
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
#include <iostream>
#include <chrono>
#include <map>
#include <random>
#include <set>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e6 + 5;

int n, m, a, b, ans;
unsigned long long sum[N];
std::vector<std::pair<int, unsigned long long>> g[N];
std::map<int, unsigned long long> map;
std::set<unsigned long long> set;

void dfs(int u, int f, unsigned long long s) {
    sum[u] = sum[f] ^ s;

    for (auto e : g[u]) {
        int v = e.first;
        unsigned long long w = e.second;

        if (v == f) continue;

        dfs(v, u, w);
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    std::mt19937_64 rand(std::chrono::system_clock::now().time_since_epoch().count());

    cin >> n >> m;

    for (int i = 1; i < n; i++) {
        int u, v, w;

        cin >> u >> v >> w;

        if (!map.count(w)) map[w] = rand();
        set.insert(map[w]);
        g[u].emplace_back(v, map[w]);
        g[v].emplace_back(u, map[w]);
    }

    dfs(1, 0, 0);

    cin >> a >> b;

    while (m--) {
        int x = a % n + 1,
            y = b % n + 1;

        unsigned long long s = sum[x] ^ sum[y];

        if (s == 0 || set.count(s)) ans++;

        a = static_cast<long long>(a) * 666073 % 1000000007;
        b = static_cast<long long>(b) * 233 % 998244353;
    }

    cout << ans << endl;

    return 0;
}