QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133540#4941. Tree Beautysalvator_noster#WA 48ms22300kbC++142.3kb2023-08-02 10:50:072023-08-02 10:50:37

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 10:50:37]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:22300kb
  • [2023-08-02 10:50:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 100000 + 5;
const int lim = 17;

int N, Q, cnt[MAX_N][20], fa[MAX_N], son[MAX_N], bro[MAX_N], dfsn[MAX_N][2], Tm;
struct SegmentNode{
    ll sum, lazy;
}node[1 << 18];
ll f[MAX_N][20], val_in[MAX_N];

void segment_modify(int i, int l, int r, int ql, int qr, int v) {
    if (l < ql || r > qr) {
        int mid = l + r >> 1;
        if (ql <= mid) segment_modify(i << 1, l, mid, ql, qr, v);
        if (mid < qr) segment_modify(i << 1 | 1, mid + 1, r, ql, qr, v);
        node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum + node[i].lazy;
    }else {
        node[i].sum += v;
        node[i].lazy += v;
    }
}

ll segment_query(int i, int l, int r, int ql, int qr) {
    if (l < ql || r > qr) {
        ll res = 0;
        int mid = l + r >> 1;
        if (ql <= mid) res = segment_query(i << 1, l, mid, ql, qr);
        if (mid < qr) res += segment_query(i << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }else {
        return node[i].sum;
    }
}

void dfs_init(int u) {
    dfsn[u][0] = ++ Tm;
    cnt[u][0] = 1;
    for (int v = son[u]; v; v = bro[v]) {
        dfs_init(v);
        for (int i = 1; i <= lim; i ++) cnt[u][i] += cnt[v][i - 1];
    }
    dfsn[u][1] = Tm;
}

void modify(int x, int y, int k) {
    if (k == 1) {
        segment_modify(1, 1, N, dfsn[x][0], dfsn[x][1], y);
        return ;
    }
    for (int i = 0, d = y; d > 0; i ++, d /= k) {
        f[x][i] += d;
        val_in[x] += 1ll * d * cnt[x][i];
    }
}

ll query(int x) {
    ll res = val_in[x] + segment_query(1, 1, N, dfsn[x][0], dfsn[x][1]);
    for (int i = 1, u = fa[x]; u && i <= lim; i ++, u = fa[u]) {
        for (int j = 0; j + i <= lim; j ++) {
            res += f[u][i + j] * cnt[x][j];
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &N, &Q);
    for (int i = 2; i <= N; i ++) {
        scanf("%d", fa + i);
        bro[i] = son[fa[i]];
        son[fa[i]] = i;
    }
    dfs_init(1);
    while (Q --) {
        int ty, x, y, k;
        scanf("%d%d", &ty, &x);
        if (ty == 1) {
            scanf("%d%d", &y, &k);
            modify(x, y, k);
        }else {
            printf("%lld\n", query(x));
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7980kb

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: 5796kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 48ms
memory: 22300kb

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:

1146255
1146255
1146255
0
2146453
182605
2146453
1153032
2146453
2146453
3748414
5131793
1642639
1068951
5278306
7035950
4817365
4817365
4817365
25477487
15963694
9961903
7749333
7405021
13755364
11010482
0
7626527
8099811
6445290
0
25002082
164454
1068951
7131073
6535995
164454
12632913
37
19439931...

result:

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