The F in cfdiv2 #907 is Niuke’s original question. I have passed it a lot. As a data structure expert, I have never done it. It is said to be very classic, but it is really bad, so I did this question the next day.
Niuke: Huahua and Yueyue Plant Trees (nowcoder.com)
cf:Problem-F-Codeforces
Niuke’s description of the topic (similar to cf’s): There are n operations:
1 i: Indicates that nodeihas grown a new son node with a weight of 0 and a number of the current maximum number + 1.2 i a: Addato the node in the subtree rooted ati3 i: Ask for the weight of theinode
Since this question is dynamic, it cannot be obtained in one go, but it cannot be built each time by adding points. But it is found that what we are looking for is the weight of the ith node. According to the properties of dfs order, we can find the dfs order of the final state. Since each node is a child node of one of the existing nodes, after building the line segment tree using the final dfs order, when traversing n times:
- If it is a point adding operation, then you need to record the weight of the current point, because before this point is added, the weight of the point must be 0, but the previous operation may have been performed on the ancestor node of the point in the final state. 2, you need to add the previous point The weighted value of this point is cancelled, so it is necessary to record the weight of the point before adding it. When the point is queried later, the answer is to find the value of the point minus org [the dfs order subscript corresponding to the point] (the org array is: the weight of the point before adding the point.
- The interval operation is the same as the basic segment tree
- Query point
i:ipoint weight minus org [dfs order subscript corresponding toipoint]
So the code is implemented as:
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;
// #define Multiple_groups_of_examples
#define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false); // When opening IOS, you need to ensure that only the Cpp io stream is used *
#define dbgnb(a) std::cout << #a << " = " << a << '\
';
#define dbgtt cout<<" !!!test!!! "<<'\
';
#define rep(i,x,n) for(int i = x; i <= n; i + + )
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second
typedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;
struct SegTree {<!-- -->
static const int N = 1e6 + 21;
struct node {<!-- -->
int l, r, mi;
LL sum,add;
}tr[N << 2];
int w[N];
// left subtree
inline int ls(int p) {<!-- -->return p<<1; }
//right subtree
inline int rs(int p) {<!-- -->return p<<1|1; }
//update up
void pushup(int u) {<!-- -->
tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
tr[u].mi = min(tr[ls(u)].mi, tr[rs(u)].mi);
}
// When tracing back, update first
void pushdown(int u) {<!-- --> // Lazy mark, the node has been modified, but its child nodes have not yet been updated.
auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];
if(root.add) {<!-- -->
right.add + = root.add; right.sum + = (LL)(right.r - right.l + 1)*root.add; right.mi -= root.add;
left.add + = root.add; left.sum + = (LL)(left.r - left.l + 1)*root.add; left.mi -= root.add;
root.add = 0;
}
}
// Build a tree
void build(int u, int l, int r) {<!-- -->
if(l == r) tr[u] = {<!-- -->l, r, w[r], w[r], 0};
else {<!-- -->
tr[u] = {<!-- -->l,r}; // easy to forget
int mid = l + r >> 1;
build(ls(u), l, mid), build(rs(u), mid + 1, r);
pushup(u);
}
}
// Revise
void modify(int u, int l, int r, int d) {<!-- -->
if(tr[u].l >= l & amp; & amp; tr[u].r <= r) {<!-- -->
tr[u].sum + = (LL)(tr[u].r - tr[u].l + 1)*d;
tr[u].add + = d;
}
else {<!-- -->
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(ls(u), l ,r, d);
if(r > mid) modify(rs(u), l, r, d);
pushup(u);
}
}
// Inquire
LL query(int u, int l, int r) {<!-- -->
if(tr[u].l >= l & amp; & amp; tr[u].r <= r) {<!-- -->
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if(l <= mid) sum = query(ls(u), l, r);
if(r > mid ) sum + = query(rs(u), l, r);
return sum;
}
}tree;
// Use fast reading when the input data is larger than 1e6
inline int fread() // fast reading
{<!-- -->
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {<!-- -->if (ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' & amp; & amp; ch <= '9') {<!-- -->
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * f;
}
void inpfile();
void solve() {<!-- -->
int n = fread();
vector<int> a(n + 1);
vector<vector<int>> g(n + 1);
//Offline storage operation
vector<array<int,3>> ask(n);
int now = 1; // now adds dot number
for(int i = 0; i < n; + + i) {<!-- -->
ask[i][0] = fread(), ask[i][1] = fread();
ask[i][1] + + ;
if(ask[i][0] == 1) {<!-- -->
int u = ask[i][1];
// The order is given here. i is the parent node, so there is no need to build bilateral sides.
g[u].push_back( + + now);
//Save the added point number into
ask[i][2] = now;
} else if(ask[i][0] == 2) ask[i][2] = fread();
}
// dfs order method
vector<int> l(n + 1), r(n + 1);
int cnt = 0;
auto dfs = [ & amp;](auto & amp; & amp;self, int u, int fa) -> void {<!-- -->
l[u] = + + cnt;
for(auto y: g[u]) {<!-- -->
if(y == fa) continue;
self(self, y,u);
}
r[u] = cnt;
};
dfs(dfs, 1,-1);
// Build a tree
tree.build(1,1,now);
vector<int> org(n + 1);
for(int i = 0; i < n; + + i) {<!-- -->
// Operation 1: Obtain how much the weight of point v was added before point v was inserted.
if(ask[i][0] == 1) {<!-- -->
int v = ask[i][2], u = ask[i][1];
org[l[v]] + = tree.query(1, l[u], l[u]);
} else if(ask[i][0] == 2) {<!-- --> // Just modify it normally
int x = ask[i][1], y = ask[i][2];
tree.modify(1,l[x], r[x], y);
} else {<!-- -->
int x = ask[i][1];
// Query value - how much x was added before insertion
cout<<tree.query(1, l[x], l[x]) - org[l[x]]<<'\
';
}
}
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif
{<!-- -->
#ifdef Multiple_groups_of_examples
int T; cin>>T;
while(T--)
#endif
solve();
return 0;
}
void inpfile() {<!-- -->
#definemytest
#ifdef mytest
freopen("ANSWER.txt", "w",stdout);
#endif
}
cfdiv2 #907F is the final output of all node weights. The array needs to be larger, otherwise it will be wa35. (I feel that Niuke’s data is weak. There is no cf 35th data. That data may be n operations and all are insertion points.
cfdiv2 #907F AC code:
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;
#define Multiple_groups_of_examples
#define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false); // When opening IOS, you need to ensure that only the Cpp io stream is used *
#define dbgnb(a) std::cout << #a << " = " << a << '\
';
#define dbgtt cout<<" !!!test!!! "<<'\
';
#define rep(i,x,n) for(int i = x; i <= n; i + + )
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second
typedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
// const int N = 2e5 + 21;
struct SegTree {<!-- -->
static const int N = 5e5 + 21;
struct node {<!-- -->
int l, r, mi;
LL sum,add;
}tr[N << 2];
int w[N];
// left subtree
inline int ls(int p) {<!-- -->return p<<1; }
//right subtree
inline int rs(int p) {<!-- -->return p<<1|1; }
//update up
void pushup(int u) {<!-- -->
tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
tr[u].mi = min(tr[ls(u)].mi, tr[rs(u)].mi);
}
// When tracing back, update first
void pushdown(int u) {<!-- --> // Lazy mark, the node has been modified, but its child nodes have not yet been updated.
auto &root = tr[u], &right = tr[rs(u)], &left = tr[ls(u)];
if(root.add) {<!-- -->
right.add + = root.add; right.sum + = (LL)(right.r - right.l + 1)*root.add; right.mi -= root.add;
left.add + = root.add; left.sum + = (LL)(left.r - left.l + 1)*root.add; left.mi -= root.add;
root.add = 0;
}
}
// Build a tree
void build(int u, int l, int r) {<!-- -->
if(l == r) tr[u] = {<!-- -->l, r, w[r], w[r], 0};
else {<!-- -->
tr[u] = {<!-- -->l,r}; // easy to forget
int mid = l + r >> 1;
build(ls(u), l, mid), build(rs(u), mid + 1, r);
pushup(u);
}
}
// Revise
void modify(int u, int l, int r, int d) {<!-- -->
if(tr[u].l >= l & amp; & amp; tr[u].r <= r) {<!-- -->
tr[u].sum + = (LL)(tr[u].r - tr[u].l + 1)*d;
tr[u].add + = d;
}
else {<!-- -->
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(ls(u), l ,r, d);
if(r > mid) modify(rs(u), l, r, d);
pushup(u);
}
}
// Inquire
LL query(int u, int l, int r) {<!-- -->
if(tr[u].l >= l & amp; & amp; tr[u].r <= r) {<!-- -->
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if(l <= mid) sum = query(ls(u), l, r);
if(r > mid ) sum + = query(rs(u), l, r);
return sum;
}
}tree;
// Use fast reading when the input data is larger than 1e6
inline int fread() // fast reading
{<!-- -->
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {<!-- -->if (ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' & amp; & amp; ch <= '9') {<!-- -->
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * f;
}
void inpfile();
void solve() {<!-- -->
int n = fread();
vector<int> a(n + 1);
vector<vector<int>> g(n + 21);
vector<array<int,3>> ask(n);
int now = 1;
for(int i = 0; i < n; + + i) {<!-- -->
ask[i][0] = fread(), ask[i][1] = fread();
// ask[i][1] + + ;
if(ask[i][0] == 1) {<!-- -->
int u = ask[i][1];
g[u].push_back( + + now);
ask[i][2] = now;
} else if(ask[i][0] == 2) ask[i][2] = fread();
}
vector<int> l(n + 21), r(n + 21);
int cnt = 0;
auto dfs = [ & amp;](auto & amp; & amp;self, int u, int fa) -> void {<!-- -->
l[u] = + + cnt;
for(auto y: g[u]) {<!-- -->
if(y == fa) continue;
self(self, y,u);
}
r[u] = cnt;
};
dfs(dfs, 1,-1);
// for(int i = 1; i <= n; + + i) tree.w[l[i]] = 0;
tree.build(1,1,now);
vector<int> org(n + 21);
for(int i = 0; i < n; + + i) {<!-- -->
if(ask[i][0] == 1) {<!-- -->
int v = ask[i][2], u = ask[i][1];
org[l[v]] + = tree.query(1, l[u], l[u]);
} else if(ask[i][0] == 2) {<!-- -->
int x = ask[i][1], y = ask[i][2];
tree.modify(1,l[x], r[x], y);
} else {<!-- -->
// int x = ask[i][1];
// cout<<tree.query(1, l[x], l[x]) - org[l[x]]<<' ';
}
}
for(int i = 1; i <= now; + + i) cout<<tree.query(1, l[i], l[i]) - org[l[i]]<<" ";
puts("");
for(int i = 0; i <= n; + + i) tree.w[i] = 0;
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif
{<!-- -->
#ifdef Multiple_groups_of_examples
int T; cin>>T;
while(T--)
#endif
solve();
return 0;
}
void inpfile() {<!-- -->
#definemytest
#ifdef mytest
freopen("ANSWER.txt", "w",stdout);
#endif
}