QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133959#4941. Tree BeautyPanC_akeWA 36ms29452kbC++202.1kb2023-08-02 18:45:582023-08-02 18:46:02

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 18:46:02]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:29452kb
  • [2023-08-02 18:45:58]
  • 提交

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 tr[maxn];

    void init(int _n) {
        n = _n;
        for (int i = 0; i <= n; i++) {
            tr[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)) tr[i] += c;
    }

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

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

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

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

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) {
        tr.modify(lid[u], rid[u], x);
        return;
    }
    for(int i = 0; i <= M; i++) {
        tag[u][i] += x;
        x /= k;
    }
}

int calc(int u) {
    int res = tr.query(lid[u], rid[u]);
    int t = 18, v = 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);
    tr.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: 13672kb

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: 2ms
memory: 10104kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 36ms
memory: 29452kb

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
0
904
0
0
0
0
0
0
15055
0
1
0
0
0
0
22466948
11068383
0
0
0
5581450
12647
0
74989
12344
168565
0
13873415
0
82227
678760
83682
0
428340
37
7300774
0
0
25588
0
1149
1
2411
853642
2271658
4519
1428255
29221408
1055918
673347
86447
14014268
115287
105355
0
0
41738487
931903
5408984
1
2910678
18...

result:

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