خانواده بلک یکی از اصیل ترین خانوادهها میان خانوادههای جادوگری است و همه اعضای آن به…
- User
خانواده بلک یکی از اصیل ترین خانوادهها میان خانوادههای جادوگری است و همه اعضای آن به شجرهنامه خانواده خود بسیار اهمیت میدهند. شجرهنامه این خانواده به شکل یک درخت است و ریشه آن بزرگترین فرد خانواده بلک است. در این خانواده سنتهای زیادی وجود دارد. مثلن گاهی یکی از اعضای خانواده تصمیم میگیرد جایزهای برای بچههایش بگیرد. نحوه جایزه دادن به این صورت است که فرد جایزهدهنده در آن روز جایزه را پیش خودش نگهمیدارد و فردایش آن جایزه را به یکی از فرزندانش (در صورت وجود) میدهد. در صورتی که آن شخص، فرزندی نداشته باشد جایزه پیش خودش میماند. وگرنه فرزندش همین کار را تکرار میکند. یعنی جایزه را یک روز پیش خود نگه میدارد و فردایش آن را به یکی از فرزندانش میدهد. این کار آنقدر تکرار میشود تا جایزه به یکی از بلکهای جوان برسد. (منظور عضوی از خانوادهاست که هنوز فرزندی ندارد یعنی یکی از برگهای درخت شجرهنامه)
با گرفتن زمان جایزه فرستادنها و شخصفرستنده جایزه به سوالاتی شبیه سوال زیر پاسخ دهید:
یک عضو جوان خانواده بلک تا یک روز مشخص حداکثر چند جایزه گرفته است؟ ورودی در خط اول ورودی دو عدد n و q آمده اند که n تعداد اعضای خانواده بلک و q تعداد استفسارات (queryها) را نشان میدهد. در خط بعد n-1 عدد p 2 . . . p n p 2 ...p n آمده است که شجره نامه خانواده بلک را مشخص میکند. فرض کنید اعضای خانواده به ترتیب سن با اعداد 1 تا n شمارهگذاری شدهاند. عدد p i p i شماره پدر(یا مادر) عضو شماره i را نشان میدهد. رأس شماره 1 اولین عضو خانواده بلک است.
در هر یک از q خط بعد در هر خط یک استفسار آمده است. در اول هر خط یک کاراکتر آمده است که نوع استفسار را مشخص میکند. کاراکتر $ نشان دهنده جایزه دادن و ? نشان دهنده پرسش است.
در حالت $، در ادامه دو عدد v و t آمده است که نشان میدهد عضو شماره vام خانواده در روز t تصمیم میگیرد جایزه بخرد! دقت کنید که یک نفر ممکن است جوان باشد و برای خودش جایزه بگیرد.
در حالت ?، در ادامه دو عدد v و t آمده است که نشان میدهد عضو شماره vآم خانواده از ابتدا تا روز t (شامل خود این روز) حداکثر چند جایزه گرفته است؟ تضمین میشود که این عضو یک بلک جوان است(فرزندی ندارد).
استفسارات به ترتیب نانزولی برحسب زمان در ورودی ظاهر شدهاند.
2 ≤ n ≤ 200
000 2≤n≤200 000 1 ≤ p i ≤ i − 1 , 2 ≤ i ≤ n 1≤p i ≤i−1,2≤i≤n
1 ≤ q ≤ 200
000 1≤q≤200 000
1 ≤ v ≤ n 1≤v≤n
1 ≤ t ≤ 1 0 9 1≤t≤10 9
خروجی در خروجی به ازای هر پرسش، جواب آن را در یک خط چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۵ n , q ≤ 2
000 n,q≤2 000 ۲ ۱۰ n , q ≤ 50
000 n,q≤50 000 و هر خانواده حداکثر یک بچه دارد. (گراف شجرهنامه یک مسیر است.) ۳ ۵۵ n , q ≤ 50
000 n,q≤50 000 ۴ ۲۰ بدون محدودیت اضافی مثال ورودی نمونه 5 8 1 2 2 1 1 4 $ 2 4 ? 3 4 ? 3 5 ? 3 6 ? 5 6 Plain text خروجی نمونه 1 1 2 3 1 c++
- Assistant
To solve this problem efficiently, we'll utilize a combination of Heavy-Light Decomposition (HLD) and Binary Indexed Trees (BIT). Here's a step-by-step breakdown of the approach:
1. Understanding the Problem
- We have a family tree where each member can give awards on certain days.
- An award propagates down the family tree, moving from parent to child each day until it reaches a leaf node (a member without children).
- We need to answer queries about how many awards a specific leaf has received up to a certain day.
2. Key Observations
- Tree Structure: The family tree is represented as a rooted tree with node
1as the root. - Leaf Nodes: Queries are only about leaf nodes.
- Propagation Condition: For a leaf node
lto receive an award from nodevon dayt, the award must propagate fromvtolwithintdays. - Transformed Condition: By defining
t_diff = t - depth(l), we can transform the condition tos' - depth(v') <= t_diff, wheres'is the day the award was given.
3. Solution Strategy
-
Heavy-Light Decomposition (HLD):
- Break down the tree into chains for efficient path queries.
- Assign each node a unique position in a linear array.
-
Binary Indexed Tree (BIT):
- Use BIT to keep track of the number of awards received by nodes up to certain positions in the HLD.
-
Event Sorting:
- Treat both award giveaways (
$operations) and queries (?operations) as events. - Sort all events based on
t_diffin ascending order. For events with the samet_diff, process award giveaways before queries to ensure correct counts.
- Treat both award giveaways (
-
Processing Events:
- Traverse the sorted events.
- For each award giveaway, update the BIT at the corresponding node's position.
- For each query, use HLD to sum the number of awards along the path from the queried leaf to the root.
4. Implementation Details
- Tree Representation: Use adjacency lists to represent the tree.
- HLD Implementation: Assign
head,position, and other necessary properties to each node. - BIT Operations: Implement standard BIT operations (
updateandquery) to handle range sum queries. - Handling Queries: For each query, calculate the required
t_diffand use HLD paths to determine the number of awards received.
5. Example Walkthrough
Consider the sample input:
5 8 1 2 2 1 $ 2 1 ? 3 3 $ 1 4 $ 2 4 ? 3 4 ? 3 5 ? 3 6 ? 5 6Following the strategy:
- Identify the tree structure and leaf nodes.
- Assign HLD positions.
- Sort and process events based on
t_diff. - Update BIT and answer queries accordingly.
6. Final Answer
Here's the complete C++ implementation based on the above strategy:
#include <bits/stdc++.h> using namespace std; typedef long long ll; // BIT implementation (1-based) struct BIT { int n; vector<int> tree; BIT(int size) : n(size), tree(size + 1, 0) {} void update(int idx, int delta=1){ while(idx <= n){ tree[idx] += delta; idx += idx & -idx; } } int query(int idx) const{ int res = 0; int i = idx; while(i >0){ res += tree[i]; i -= i & -i; } return res; } // Query sum from l to r inclusive int query(int l, int r) const{ if(l > r) return 0; return query(r) - query(l-1); } }; // HLD implementation struct HLD { int n; vector<vector<int>> adj; vector<int> parent; vector<int> depth; vector<int> heavy; vector<int> head; vector<int> pos; int cur_pos; HLD(int size) : n(size), adj(size +1, vector<int>()), parent(size +1, 0), depth(size +1, 0), heavy(size +1, -1), head(size +1, 0), pos(size +1, 0), cur_pos(1) {} void add_edge(int u, int v){ adj[u].push_back(v); adj[v].push_back(u); } // DFS to compute sizes and heavy child int dfs(int v, int p_node){ parent[v] = p_node; int size =1; int max_size = 0; for(auto &u: adj[v]){ if(u != p_node){ depth[u] = depth[v] +1; int sz = dfs(u, v); size += sz; if(sz > max_size){ max_size = sz; heavy[v] = u; } } } return size; } // Decompose the tree void decompose(int v, int h){ head[v] = h; pos[v] = cur_pos++; if(heavy[v] != -1){ decompose(heavy[v], h); for(auto &u: adj[v]){ if(u != parent[v] && u != heavy[v]){ decompose(u, u); } } } } // Initialize HLD void build(int root=1){ dfs(root, -1); decompose(root, root); } // Query the path from u to v (assuming v is ancestor of u) int query_path(int u, const BIT &bit) const{ int res =0; while(head[u] != head[1]){ res += bit.query(pos[head[u]], pos[u]); u = parent[head[u]]; } res += bit.query(pos[1], pos[u]); return res; } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<int> p(n+1, 0); // Read p2 to pn for(int i=2;i<=n;i++) cin >> p[i]; // Build tree HLD hld(n); for(int i=2;i<=n;i++) { hld.add_edge(p[i], i); } // Compute depth and HLD hld.build(1); // Identify leaves vector<bool> is_leaf(n+1, true); for(int i=2;i<=n;i++) is_leaf[p[i]] = false; // Read all events struct Query { int id; int l; ll t; }; struct Update { ll t_diff; int v; }; struct Event { ll t_diff; int type; // 0 for update, 1 for query int v; // for update: node v; for query: leaf l int qid; // for query }; vector<Event> events; int query_count =0; vector<Query> queries; // To store answers vector<int> answer(q, 0); for(int i=0;i<q;i++){ char c; cin >> c; if(c == '$'){ int v; ll s; cin >> v >> s; ll t_diff = s - hld.depth[v]; events.push_back(Event{t_diff, 0, v, -1}); } else { // '?' int l; ll t; cin >> l >> t; // Assuming l is a leaf ll t_diff = t - hld.depth[l]; events.push_back(Event{t_diff, 1, l, query_count}); queries.push_back(Query{query_count, l, t}); query_count++; } } // Sort events by t_diff ascendingly, type 'update' before 'query' for same t_diff sort(events.begin(), events.end(), [&](const Event &a, const Event &b) -> bool{ if(a.t_diff != b.t_diff) return a.t_diff < b.t_diff; return a.type < b.type; // 0 ('update') before 1 ('query') }); // Initialize BIT BIT bit(n); // Process events for(auto &e: events){ if(e.type ==0){ // Update: insert into BIT bit.update(hld.pos[e.v], 1); } else{ // Query if(e.t_diff <0){ answer[e.qid] =0; } else{ // Perform path query from l to root int l = e.v; // Ensure l is a leaf // Sum over path from l to root // Using HLD // Implemented as a separate function // But here, we implement it inline int res =0; while(hld.head[l] != hld.head[1]){ res += bit.query(hld.pos[hld.head[l]], hld.pos[l]); l = hld.parent[hld.head[l]]; } res += bit.query(hld.pos[1], hld.pos[l]); answer[e.qid] = res; } } } // Output answers in the order of input queries for(int i=0;i<query_count;i++) cout << answer[i] << "\n"; }