QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244427#4941. Tree Beautyrgnerdplayer#WA 46ms40916kbC++202.7kb2023-11-09 02:24:552023-11-09 02:24:55

Judging History

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

  • [2023-11-09 02:24:55]
  • 评测
  • 测评结果:WA
  • 用时:46ms
  • 内存:40916kb
  • [2023-11-09 02:24:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int n = 0) : n(n), a(n) {}
    void add(int p, T v) {
        while (p < n) {
            a[p] += v;
            p |= p + 1;
        }
    }
    T sum(int p) {
        T res = {};
        while (p >= 0) {
            res += a[p];
            p = (p & p + 1) - 1;
        }
        return res;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    auto solve = [&]() {
        int n, q;
        cin >> n >> q;

        vector<vector<int>> adj(n);
        for (int i = 1; i < n; i++) {
            int p;
            cin >> p;
            adj[--p].push_back(i);
        }

        constexpr int K = 20;

        vector<int> dep(n), par(n, -1), tin(n), tout(n), sz(n, 1);
        vector childCnt(n, vector<int>(K));
        int T = 0;

        auto dfs = [&](auto dfs, int u) -> void {
            tin[u] = T++;
            childCnt[u][0]++;
            for (auto v : adj[u]) {
                dep[v] = dep[u] + 1;
                par[v] = u;
                dfs(dfs, v);
                sz[u] += sz[v];
                for (int i = 1; i < K; i++) {
                    childCnt[u][i] += childCnt[v][i - 1];
                }
            }
            tout[u] = T;
        };
        dfs(dfs, 0);

        Fenwick<i64> f(n), g(n);
        vector childAdd(n, vector<i64>(K));

        while (q--) {
            int op;
            cin >> op;

            if (op == 1) {
                int x, y, k;
                cin >> x >> y >> k;
                x--;

                if (k == 1) {
                    f.add(tin[x], y);
                    f.add(tin[x], -y);
                    g.add(tin[x], 1LL * sz[x] * y);
                } else {
                    i64 s = 0;
                    for (int i = 0; i < K; i++) {
                        childAdd[x][i] += y;
                        s += 1LL * childCnt[x][i] * y;
                        y /= k;
                    }
                    g.add(tin[x], s);
                }
            } else {
                int x;
                cin >> x;
                x--;
                i64 ans = f.sum(tin[x]) * sz[x] + g.sum(tout[x] - 1) - g.sum(tin[x]);

                int u = x;
                for (int i = 0; i < K && u != -1; i++) {
                    for (int j = 0; i + j < K; j++) {
                        ans += childAdd[u][i + j] * childCnt[x][j];
                    }
                    u = par[u];
                }

                cout << ans << '\n';
            }
        }
    };
    
    solve();
    
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3524kb

input:

5 5
1 1 3 3
1 1 99 2
2 1
2 3
1 3 2 3
2 3

output:

245
97
99

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 46ms
memory: 40916kb

input:

100000 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1818724600
1818724600
1818724600
0
2920352548
904
2920352548
1101627948
2920352548
2920352548
4492303477
5061484915
555127744
526252800
5061750398
11569471874
5034373536
5034373536
5034373536
2072854996
4981808979
26872020588
13921067785
10829155036
12550680652
25699267461
0
9006876736
12502182908
8...

result:

wrong answer 4th lines differ - expected: '672469600', found: '0'