前言
以此纪念 1:59:14 过的 Div.2 F。
题目翻译
有一棵以 $1$ 为根的有根树，一开始只有节点 $1$。
有 $q(1\leq q\leq 5\times 10^5)$ 个操作：
1 u 表示添加一条 $u\to sz+1$ 的边，其中 $sz$ 为目前树的大小。
2 u w 表示对于以 $u$ 为根的子树，对于所有节点添加 $w(-10^9\leq w\leq 10^9)$ 的权重。
$q$ 次操作后，输出当前树上每个节点的权重。
题目思路
题目不强制在线，我们考虑先离线操作。
离线之后先按操作建出最终状态的树。此时权重都为 $w$。
然后套路性的把这棵树按 Euler Tour 压成一段序列。压好之后同一子树内的节点肯定是连续出现的。
此时 2 操作维护区间加法。操作 1 维护区间清零，因为如果这个点没被建出不会存在以它为根的修改操作，也就是说区间内的数都是一样的，相当于区间加法了。
所以维护区间加法和单点查询操作即可。可以使用 BIT 或 SGT。代码使用的是 BIT。
完整代码
读入量巨大，建议使用快读！
一些东西的用处：
ll cur_tree_sz=1; 当前树大小。
vector<pii> a[2000020]; 建树。
ll in[2000020];ll out[2000020]; Euler Tour 中的左右端点，即最早最晚的出现次数。
ll times; Euler Tour 的时间（长度）。
ll c[4000020]; BIT 数组。change 进行单点修改，query 进行单点查询。区间修改只需要用单点修改差分即可。
赛时着急写得有点拉，上述没提到的部分东西其实没用。
#include <bits/stdc++.h>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
inline T read()
{
register T x = 0;
register int f = 1;
register char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
f = -f;
for (; c >= '0' && c <= '9'; c = getchar())
x = (x << 1) + (x << 3) + (c ^ 48);
return x * f;
}
typedef long long ll;
typedef pair<ll, ll> pii;
int Q;
ll cur_tree_sz = 1;
struct Query
{
ll op, x, y, t;
} q[2000020];
vector<pii> a[2000020];
ll dep[2000020];
ll in[2000020];
ll out[2000020];
ll id[2000020];
ll times;
// 树按dfs拍成序列
void dfs(int u, int fa, int d)
{
dep[u] = d;
in[u] = ++times;
id[++times] = u;
for (pii p : a[u])
{
ll v = p.first, j = p.second;
if (v == fa)
continue;
dfs(v, u, d + 1);
}
out[u] = ++times;
}
ll c[4000020];
const int N = 4000000;
ll lowbit(ll x)
{
return x & -x;
}
ll query(ll x)
{
ll ret = 0;
while (x)
{
ret += c[x];
x -= lowbit(x);
}
return ret;
}
void change(ll x, ll y)
{
while (x <= N)
{
c[x] += y;
x += lowbit(x);
}
}
void solve()
{
for (int i = 1; i <= cur_tree_sz + 10; i++)
dep[i] = id[i] = in[i] = out[i] = 0, a[i].clear();
for (int i = 1; i <= times + 10; i++)
c[i] = 0;
cur_tree_sz = 1;
times = 0;
Q = read<int>();
for (int i = 1; i <= Q; i++)
{
q[i].op = read<int>();
q[i].x = read<int>();
if (q[i].op & 1)
{
a[q[i].x].push_back({++cur_tree_sz, ++times});
}
else
{
q[i].y = read<ll>();
}
q[i].t = i;
}
times = 0;
dfs(1, 0, 1);
cur_tree_sz = 1;
for (int i = 1; i <= Q; i++)
{
if (q[i].op & 1)
{
cur_tree_sz++;
ll res = query(in[cur_tree_sz]);
change(in[cur_tree_sz], -res);
change(out[cur_tree_sz], res);
}
else
{
change(in[q[i].x], q[i].y);
change(out[q[i].x], -q[i].y);
}
}
// for (int i = 1; i <= cur_tree_sz; i++)
// cout << id[i] << " ";
// cout << endl;
for (int i = 1; i <= cur_tree_sz; i++)
printf("%lld ", query(in[i]));
printf("\n");
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}