QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133981#4941. Tree BeautyPanC_akeWA 31ms35520kbC++202.6kb2023-08-02 19:29:142023-08-02 19:29:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 19:29:14]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:35520kb
  • [2023-08-02 19:29:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int maxn = 100010;
const int M = 18;

template <typename T>
struct BIT {
    int n;
    T tr1[maxn], tr2[maxn];

    void init(int _n) {
        n = _n;
        for (int i = 0; i <= n; i++) {
            tr1[i] = tr2[i] = T();
        }
    }

    inline int lowbit(int x) { return x & -x; }

    void add(int x, T c) {
        for (int i = x; i <= n; i += lowbit(i)) tr1[i] += c;
        for (int i = x; i <= n; i += lowbit(i)) tr2[i] += x * c;
    }

    void modify(int l, int r, T c) {
        add(l, c);
        if (r + 1 <= n) add(r + 1, -c);
    }

    T query1(int x) {
        T res = T();
        for (int i = x; i; i -= lowbit(i)) res += tr1[i];
        return res;
    }

    T query2(int x) {
        T res = T();
        for (int i = x; i; i -= lowbit(i)) res += tr2[i];
        return res;
    }

    T query_cf(int x) { return (x + 1) * query1(x) - query2(x); }

    T query_cf(int l, int r) { return query_cf(r) - query_cf(l - 1); }

    T query(int l, int r) { return query1(r) - query1(l - 1); }
};

int n, q, tot;
int dep[maxn], p[maxn], lid[maxn], rid[maxn], son[maxn][M + 1],
    tag[maxn][M + 1];
vector<int> e[maxn];
BIT<int> b1, b2;

void dfs(int u, int f) {
    lid[u] = ++tot;
    son[u][0] = 1;
    dep[u] = dep[f] + 1;
    for (int v : e[u]) {
        dfs(v, u);
        for (int i = 1; i <= M; i++) son[u][i] += son[v][i - 1];
    }
    rid[u] = tot;
}

void addtag(int u, int x, int k) {
    if (k == 1) {
        b1.modify(lid[u], rid[u], x);
        return;
    }
    int add = 0;
    for (int i = 0; i <= M; i++) {
        add += son[u][i] * x;
        tag[u][i] += x;
        x /= k;
    }
    b2.add(lid[u], add);
}

int calc(int u) {
    int res = b1.query(lid[u], rid[u]) + b2.query(lid[u], rid[u]);
    int v = p[u];
    while (v) {
        if (dep[v] + 18 < dep[u]) break;
        for (int i = 0; dep[v] + 18 >= dep[u] + i; i++) {
            res += son[u][i] * tag[v][i + dep[u] - dep[v]];
        }
        v = p[v];
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
        e[p[i]].push_back(i);
    }
    dfs(1, 0);
    b1.init(n);
    b2.init(n);
    while (q--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int u, x, k;
            cin >> u >> x >> k;
            addtag(u, x, k);
        } else {
            int u;
            cin >> u;
            cout << calc(u) << endl;
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 11840kb

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: 1ms
memory: 13708kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 31ms
memory: 35520kb

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:

0
0
0
0
22466948
904
22466948
22466948
22466948
22466948
114959777
157888415
28874944
0
158153898
173705674
130777036
130777036
130777036
67144096
78212479
315011688
202510785
130777036
202590252
248158661
0
130852025
154092508
109173058
0
300430054
0
82227
109683253
109088175
0
341892512
37
3103543...

result:

wrong answer 1st lines differ - expected: '1818724600', found: '0'