QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133965 | #4941. Tree Beauty | dzy521 | WA | 35ms | 39488kb | C++23 | 3.2kb | 2023-08-02 18:56:47 | 2023-08-02 18:56:51 |
Judging History
answer
#define _CRT_SEstartE_NO_DEPRECATE
#pragma warning(disable : 4996)
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bits/stdc++.h>
#define ACcode ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 1e5 + 7;
const ll maxm = 1e7 + 5e6 + 7;
constexpr ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int Prime = 100007;
const double eps = 1e-5;
const double pi = acos(-1.0);
using namespace std;
struct BIT
{
ll tree1[maxn], tree2[maxn];
int n;
ll lowbit(ll x)
{
return x & (-x);
}
void addone(int x, ll y)
{
ll z = x * y;
for (; x < maxn; x += lowbit(x))
tree1[x] += y, tree2[x] += z;
}
void addall(int l, int r, ll y)
{
addone(l, y);
addone(r + 1, -y);
}
ll getpre(int x)
{
ll ans = 0, tx = x + 1;
for (; x; x -= lowbit(x))
ans += tx * tree1[x] - tree2[x];
return ans;
}
ll query(int l, int r)
{
return getpre(r) - getpre(l - 1);
}
} bit;
vector<int> g[maxn];
int fat[maxn], in[maxn], out[maxn], dfn;
ll tag[maxn][25], soncnt[maxn][25];
void dfs(int u, int fa)
{
fat[u] = fa;
soncnt[u][0] = 1;
in[u] = ++dfn;
for (auto v : g[u])
{
if (v == fa)
continue;
dfs(v, u);
for (int i = 1; i <= 20; i++)
soncnt[u][i] += soncnt[v][i - 1];
}
out[u] = dfn;
}
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 2; i <= n; i++)
{
int x;
cin >> x;
g[i].push_back(x);
g[x].push_back(i);
}
dfs(1, 0);
for (int i = 1; i <= m; i++)
{
int ope, u, y, k;
cin >> ope >> u;
if (ope == 1)
{
cin >> y >> k;
if (k == 1)
{
bit.addall(in[u], out[u], y);
continue;
}
ll res = 0;
for (int i = 0; i <= 20; i++)
{
res += soncnt[u][i] * y;
tag[u][i] += y, y /= k;
}
bit.addall(in[u], in[u], res);
}
else
{
ll ans = bit.query(in[u], out[u]);
int nowu = fat[u];
for (int i = 1; i <= 20; i++)
{
if (nowu == 0)
break;
for (int j = 1; j < 20 - i; j++)
ans += tag[nowu][j] * soncnt[u][j - 1];
nowu = fat[nowu];
}
cout << ans << '\n';
}
}
}
signed main()
{
ACcode;
// freopen("house.in", "r", stdin);
// freopen("house.out", "w", stdout);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9732kb
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: 7512kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 35ms
memory: 39488kb
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 672469600 2920352548 1998042924 2920352548 2782801948 2920352548 2920352548 7518672977 11295020015 7561459692 4390469344 19265510335 22947288874 15221147536 15428570536 14322314536 9119623396 12969816144 26872020588 25039643385 22398749036 27928613202 31553345626 745...
result:
wrong answer 6th lines differ - expected: '1987509504', found: '1998042924'