I came across this problem while practicing, but I didn't solve it, some suggestions for these types of problems would be appreciated. We have a tree with n nodes(n <= 300000), and each node has a number A(1 <= A <= 10^9). The first line of the input consists of two numbers n and A0 (the number of nodes and the number on node 1). Each of the next n-1 lines has two numbers Ai and the parent of node i. For every node except the root, we need to find the number of nodes that have a strictly smaller number than the current node. Then we need to update every node on the path from the current node to the root, set Aj = max(Aj, Ai)
Example:
5 400
350 0
300 1
450 2
420 0
550 3
Answer:
0
0
3
0
4
Can you provide me with the original statement or link to the problem?
Its from a national competition, the language is different.
Have you tried heavy-light decomposition? If you are updating some node, you will update everything up to some point on path to root. If there are k intervals of different numbers, you need to change, it will be done in something like O(log^2n + klogn) (sequence on any path to root will be ascending so we will always change some consistent interval on path). But if there are k intervals of different numbers, then they were produced by some earlier updates. Tho we have n updates, and one can produce at most logn new intervals on path to root (there are at most logn light edges on path to root). I'm not 100% sure if it works, i can try solve it and let you know if it does. Could you provide link to original statement?
Well, this is the first time I'm hearing about heavy-light decomposition, I'll do some research on the topic, and try to learn it.
Here's the link https://mendo.mk/Task.do?id=809, although I belive you will need to create an account to be able to submit the problem.
I thought that you need to tell how many smaller nodes are in the whole tree, not only on path to root. This way it's simple, standard hld. If you're intrested i got ac by this code
#include #define ll long long #define pb push_back #define ppb pop_back #define pii pair #define pll pair #define endl '\n' #define se second #define fi first #define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define mid (l+r)/2 #define mide (lo+hi)/2 #define inf 1100000000 #define vii vector #define vi vector using namespace std; const int N = 300200; const int pot = (1<<20); struct hld { int czas = 0; vector v; vi p, s, deep, pre, roz; vi mi, mx, up; hld() { v = vector(N); p = s = deep = pre = roz = vi(N); mi = mx = up = vi(pot*2); } void inline lazy(int e) { if(up[e]) { up[e*2] = up[e*2+1] = up[e]; mx[e*2] = mx[e*2+1] = up[e]; mi[e*2] = mi[e*2+1] = up[e]; up[e] = 0; } } void update(int a, int b, int val, int e = 1, int lo = 0, int hi = pot) { if(b<=a) return; if(a == lo and b == hi) { up[e] = mx[e] = mi[e] = val; return; } lazy(e); update(a, min(mide, b), val, e*2, lo, mide); update(max(a,mide), b, val, e*2+1, mide, hi); mx[e] = max(mx[e*2], mx[e*2+1]); mi[e] = min(mi[e*2], mi[e*2+1]); } int query(int a, int b, int e = 1, int lo = 0, int hi = pot) { if(b<=a) return 0; if(a == lo and b == hi) return mx[e]; lazy(e); int q1 = query(a, min(mide, b), e*2, lo, mide); int q2 = query(max(a,mide), b, e*2+1, mide, hi); mx[e] = max(mx[e*2], mx[e*2+1]); mi[e] = min(mi[e*2], mi[e*2+1]); return max(q1, q2); } void dfs_deep(int e, int pr = -1) { deep[e] = deep[pr]+1; roz[e] = 1; p[e] = pr; for(auto it : v[e]) if(it != pr) { dfs_deep(it, e); roz[e] += roz[it]; } } void dfs_pre(int e) { pre[e] = ++czas; if(roz[e] == 1) return; int mx = 0, el = -1; for(auto it : v[e]) if(p[e] != it and mx < roz[it]) { mx = roz[it]; el = it; } if(el != -1) { s[el] = s[e]; dfs_pre(el); for(auto it : v[e]) if(it != p[e] and it != el) { s[it] = it; dfs_pre(it); } } } void add_edge(int a, int b) { v[a].pb(b); v[b].pb(a); } void build_hld(int root = 1) { dfs_deep(root, root); s[root] = root; dfs_pre(root); } int special_query(int e, int val, int lo, int hi) { if(mx[e] < val) { up[e] = mx[e] = mi[e] = val; return hi-lo; } if(mi[e] >= val) return 0; lazy(e); int q1 = special_query(e*2, val, lo, mide); int q2 = special_query(e*2+1, val, mide, hi); mx[e] = max(mx[e*2], mx[e*2+1]); mi[e] = min(mi[e*2], mi[e*2+1]); return q1 + q2; } int special_query_deliver(int a, int b, int val, int e = 1, int lo = 0, int hi = pot) { if(b<=a) return 0; if(a == lo and b == hi) return special_query(e, val, lo, hi); lazy(e); int q1 = special_query_deliver(a, min(b,mide), val, e*2, lo, mide); int q2 = special_query_deliver(max(a,mide), b, val, e*2+1, mide, hi); mx[e] = max(mx[e*2], mx[e*2+1]); mi[e] = min(mi[e*2], mi[e*2+1]); return q1+q2; } int hld_query(int a, int val) { int res = 0; while(a != -1 and query(pre[s[a]], pre[a]+1) < val) { update(pre[s[a]], pre[a]+1, val); res += deep[a] - deep[s[a]]+1; a = p[s[a]]; } res += special_query_deliver(pre[s[a]], pre[a]+1, val); return res-1; } }; int main() { turbo int n, val_0; cin >> n >> val_0; hld hd; vi zap(n); for(int i = 0; i < n; i++) { int val, pr; cin >> val >> pr; hd.add_edge(i+1, pr); zap[i] = val; } hd.build_hld(0); hd.update(hd.pre[0], hd.pre[0]+1, val_0); cout << endl; for(int i = 0; i < (int)zap.size(); i++) cout << hd.hld_query(i+1, zap[i]) << endl; }Can you tell me what the dfs functions do?
And what do we store in roz(the size of the subtree?)
In the segment tree, we store maximum and minimum to answer queries for some range, correct?
dfss are to build hld structure.
Theses tables are:
roz — size of subtree
p — parent of node
s — leader of our heavy path going up (up most node on that path)
(by heavy path, i mean path consisting only heavy edges)
pre — pre order of node
In second dfs (pre_dfs) we're calculating pre_order, but we're visiting our child's in particular order. We visit our heaviest child first, and then the rest. This way all heavy paths are consistent intervals by their pre order. We also calculate paths leaders.
Doing it this way allow us to use single segment tree on all pre_orders and do updates/queries on its sub segments (we got all heavy path's on single segment tree).
Segment tree indeed stores maximum, minimum, and updates are, "set some vale on interval". If some path has maximum < val then we know we can take whole path and jump to parent of leader. If maximum >= val then we know there's no point in searching up for smaller numbers, so we just query special_query and return our answer.
Special query just count numbers smaller than val and set's them to val.
Theses special_query_deliver is needed bcs since we're keeping all heavy-paths on same segtree first we need to find their base-segments(? idk how it's called in eng), and then we can assume these segments are ascending.