QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#281728#6858. Play on TreeTaylorFlyWA 120ms20176kbC++201.5kb2023-12-10 16:48:092023-12-10 16:48:10

Judging History

你现在查看的是最新测评结果

  • [2023-12-10 16:48:10]
  • 评测
  • 测评结果:WA
  • 用时:120ms
  • 内存:20176kb
  • [2023-12-10 16:48:09]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> G(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }   
    std::vector<int> f(n);
    auto dfs1 = [&](auto self, int u, int fa) -> void {
        for (int v: G[u]) {
            if (v == fa) continue;
            self(self, v, u);
            f[u] ^= f[v] + 1;
        }
    };

    std::vector<int> ans(n);
    auto dfs2 = [&](auto self, int u, int fa) -> void {
        for (int v: G[u]) {
            if (v == fa) continue;
            ans[v] = f[v] ^ ((ans[u] ^ (ans[v] + 1)) + 1);
            self(self, v, u);
        }
    };

    dfs1(dfs1, 0, -1);
    ans[0] = f[0];
    dfs2(dfs2, 0, -1);
    constexpr int mod = 1e9 + 7;
    i64 res = 0;
    auto qmi = [&](i64 a, int k) -> int{
        i64 res = 1;
        while (k) {
            if (k & 1) res = res * a % mod;
            k >>= 1;
            a = (i64) a * a % mod;
        }
        return res % mod;
    };

    for (int i = 0; i < n; i++) {
        if (ans[i]) {
            res ++;
        }
    }    
    std::cout << res * qmi(n, mod - 2) % mod << "\n";
}


int main() {
    std::ios::sync_with_stdio(false); 
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t --)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 120ms
memory: 20176kb

input:

3
199999
144802 35753
35753 9646
9646 148183
9646 167003
9646 199831
9646 193968
9646 182279
9646 185547
9646 106896
9646 196577
9646 150627
9646 147736
9646 180949
9646 179482
9646 196999
9646 191636
9646 184859
9646 173080
9646 155500
9646 191682
9646 169619
9646 191285
9646 106525
9646 187324
964...

output:

982224919
1
888578404

result:

wrong answer 1st lines differ - expected: '256641286', found: '982224919'