【题解】HackerRank-Number Game on a Tree

Posted on Edited on In Disqus:

题目

https://www.hackerrank.com/challenges/number-game-on-a-tree/problem

题意

给一棵树，求有多少结点的有序对使得先手必胜。

对于一个有序点对，在路径上的边权集上玩一个游戏，轮流移除一个数字，要求比不超过之前移除的所有数字，无法操作者为败者。

题解

  • 首先考虑这个博弈问题：
    • 如果最小的数只有奇数个那么先手必胜。
    • 推广一下，如果最小的数有偶数个，但是次小的有奇数个，那么先手必胜。
    • 所以只要存在一个数字出现了奇数次，那么先手拿最小的出现奇数次的数字就能必胜。
  • 如果数字范围很小的话，可以把这个数对 2 取幂，那么问题就转化为了求异或和为零的路径数量了。这个问题可以通过求出每个点到根的路径异或和来很方便地求出。
  • 数字范围比较大，那么就在模意义下计算，为了安全起见，取两个模数。

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 5E5 + 100;
const LL M1 = 921997837, M2 = 988244353;
struct E {
    int to, w;
};
vector<E> G[N];
map<pair<LL, LL>, LL> mp;

LL p2(LL x, LL m) {
    LL ret = 1, t = 2;
    for (; x; x >>= 1, t = t * t % m)
        if (x & 1) ret = ret * t % m;
    return ret;
}

void dfs(int u, int fa, LL m1, LL m2) {
    mp[{m1, m2}]++;
    for (E& e: G[u]) {
        int v = e.to;
        if (v == fa) continue;
        dfs(v, u, m1 ^ p2(e.w, M1), m2 ^ p2(e.w, M2));
    }
}
inline LL C2(LL x) { return x * (x - 1) / 2; }

int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        mp.clear();
        FOR (i, 1, n + 1) G[i].clear();
        FOR (_, 1, n) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            G[u].push_back({v, w});
            G[v].push_back({u, w});
        }
        dfs(1, 1, 0, 0);
        LL ans = 0;
        for (auto& x: mp)
            ans += C2(x.second);
        ans = C2(n) - ans;
        cout << ans << endl;
    }
}